Connectivity oracles for failure prone graphs

DOI10.1145/1806689.1806754zbMath1293.05188OpenAlexW2141257824MaRDI QIDQ2875174

Ran Duan, Seth Pettie

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806754

zbMATH Keywords

connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (6)

(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Fault-Tolerant Compact Routing Schemes for General Graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Unnamed Item

This page was built for publication: Connectivity oracles for failure prone graphs