A nearly optimal oracle for avoiding failed vertices and edges
From MaRDI portal
Publication:5172703
DOI10.1145/1536414.1536431zbMath1304.68066OpenAlexW2117909275MaRDI QIDQ5172703
Aaron Bernstein, David R. Karger
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1536414.1536431
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (24)
The impact of dynamic events on the number of errors in networks ⋮ Improved Purely Additive Fault-Tolerant Spanners ⋮ Fault tolerant depth first search in undirected graphs: simple yet efficient ⋮ Mincut sensitivity data structures for the insertion of an edge ⋮ Shortest paths avoiding forbidden subpaths ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Vertex fault tolerant additive spanners ⋮ Unnamed Item ⋮ Compact distance oracles with large sensitivity and low stretch ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. ⋮ Improved distance sensitivity oracles with subcubic preprocessing time ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Fault-tolerant approximate shortest-path trees ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Incremental distance products via faulty shortest paths ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: A nearly optimal oracle for avoiding failed vertices and edges
