Cover Image

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Parter, Merav, Petruschka, Asaf
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

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

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

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

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

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

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

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

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

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)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, 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)

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

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

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

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
by: Boneh, Itai, et al.
Published: (2025)

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

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

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

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

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

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

Optimal (degree+1)-Coloring in Congested Clique
by: Coy, Sam, et al.
Published: (2023)

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

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)

A Near-Optimal Kernel for a Coloring Problem
by: Haviv, Ishay, et al.
Published: (2025)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

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

A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms
by: Kirkpatrick, Yael, et al.
Published: (2024)

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

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
by: Gorbachev, Egor, et al.
Published: (2024)

Time-Optimal Directed q-Analysis
by: Windisch, Felix, et al.
Published: (2025)

Optimal-Time Move Structure Construction
by: Brown, Nathaniel K., et al.
Published: (2026)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
by: Campbell, Jesse, et al.
Published: (2024)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2025)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

Almost Linear Size Edit Distance Sketch
by: Koucký, Michal, et al.
Published: (2024)

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