Cover Image

An Optimal $3$-Fault-Tolerant Connectivity Oracle

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Kosinas, Evangelos
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Connectivity Oracles for Predictable Vertex Failures
by: Hu, Bingbing, et al.
Published: (2023)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Nearly Optimal Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Near Optimal Dual Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

On 2-strong connectivity orientations of mixed graphs and related problems
by: Georgiadis, Loukas, et al.
Published: (2023)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

Efficient Contractions of Dynamic Graphs -- with Applications
by: Henzinger, Monika, et al.
Published: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
by: Bhanja, Koustav, et al.
Published: (2025)

Fault-Tolerant Approximate Distance Oracles with a Source Set
by: Dey, Dipan, et al.
Published: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Online Drone Scheduling for Last-mile Delivery
by: Jana, Saswata, et al.
Published: (2024)

Graph Reconstruction with a Connected Components Oracle
by: Harviainen, Juha, et al.
Published: (2025)

Optimal Sensitivity Oracle for Steiner Mincut
by: Bhanja, Koustav
Published: (2024)

Fault-Tolerant Bounded Flow Preservers
by: Bansal, Shivam, et al.
Published: (2024)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
by: Long, Yaowei, et al.
Published: (2024)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
by: Li, Xizhe, et al.
Published: (2026)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
by: He, Jialin, et al.
Published: (2025)

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
by: Bilò, Davide, et al.
Published: (2024)

Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
by: Lamprou, Ioannis, et al.
Published: (2025)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
by: Parter, Merav, et al.
Published: (2024)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
by: Parter, Merav, et al.
Published: (2024)

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
by: Long, Yaowei, et al.
Published: (2024)

An Optimal Sorting Algorithm for Persistent Random Comparison Faults
by: Geissmann, Barbara, et al.
Published: (2025)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
by: Chen, Xi, et al.
Published: (2025)

Hyper-distance Oracles in Hypergraphs
by: Preti, Giulia, et al.
Published: (2023)

Distributed Distance Sensitivity Oracles
by: Manoharan, Vignesh, et al.
Published: (2024)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Improved Algorithms for Clustering with Noisy Distance Oracles
by: Pradhan, Pinki, et al.
Published: (2026)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
by: Bilò, Davide, et al.
Published: (2024)

Path-Reporting Distance Oracles with Linear Size
by: Neiman, Ofer, et al.
Published: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
by: Bilò, Davide, et al.
Published: (2023)

Sublinear Spectral Clustering Oracle with Little Memory
by: Shen, Ranran, et al.
Published: (2026)

Fitting Tree Metrics and Ultrametrics in Data Streams
by: Carmel, Amir, et al.
Published: (2025)

Stabilizer Code-Generic Universal Fault-Tolerant Quantum Computation
by: Papadopoulos, Nicholas J. C., et al.
Published: (2026)