Cover Image

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Parter, Merav, Tzalik, Elad
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
by: Fischer, Orr, et al.
Published: (2025)

Greedy Completion for Weighted $(α,β)$-Spanners
by: Tzalik, Elad
Published: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

Connectivity Labeling in Faulty Colored Graphs
by: Petruschka, Asaf, et al.
Published: (2024)

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

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

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
by: Gil, Yuval, et al.
Published: (2025)

Distributed Interactive Proofs for Planarity with Log-Star Communication
by: Gil, Yuval, et al.
Published: (2025)

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

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

An Optimal $3$-Fault-Tolerant Connectivity Oracle
by: Kosinas, Evangelos
Published: (2025)

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

Distributed Maximum Flow in Planar Graphs
by: Abd-Elhaleem, Yaseen, et al.
Published: (2024)

Better and Simpler Reducibility Bounds over the Integers
by: Levin, Asaf
Published: (2025)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
by: Çivril, Ali
Published: (2024)

Simpler Universally Optimal Dijkstra
by: van der Hoog, Ivor, et al.
Published: (2025)

Fault-Equivalent Lowest Common Ancestors
by: Petruschka, Asaf
Published: (2024)

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

Fault-tolerant $k$-Supplier with Outliers
by: Chakrabarty, Deeparnab, et al.
Published: (2023)

The Connected k-Vertex One-Center Problem on Graphs
by: Zhang, Jingru
Published: (2024)

Simpler and Improved Replacement Path Coverings
by: Bilò, Davide, et al.
Published: (2026)

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

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

Low-Cost Arborescence Under Edge Faults
by: Dey, Dipan, et al.
Published: (2026)

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

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)

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

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
by: Wlodarczyk, Michal
Published: (2023)

3SUM in Preprocessed Universes: Faster and Simpler
by: Kasliwal, Shashwat, et al.
Published: (2024)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
by: Jiang, Yonggang, et al.
Published: (2025)

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

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

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