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




Related Items (24)

The impact of dynamic events on the number of errors in networksImproved Purely Additive Fault-Tolerant SpannersFault tolerant depth first search in undirected graphs: simple yet efficientMincut sensitivity data structures for the insertion of an edgeShortest paths avoiding forbidden subpathsEfficient Oracles and Routing Schemes for Replacement PathsVertex fault tolerant additive spannersUnnamed ItemCompact distance oracles with large sensitivity and low stretchDeterministic Fault-Tolerant Connectivity Labeling SchemeApproximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphsTruly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus ProductAn efficient strongly connected components algorithm in the fault tolerant modelImproved Distance Sensitivity Oracles with Subcubic Preprocessing Time.Improved distance sensitivity oracles with subcubic preprocessing time\(f\)-sensitivity distance oracles and routing schemesFault-tolerant approximate shortest-path treesConnectivity Oracles for Graphs Subject to Vertex FailuresDeterministic Combinatorial Replacement Paths and Distance Sensitivity OraclesMultiple-edge-fault-tolerant approximate shortest-path treesIncremental distance products via faulty shortest pathsSparse Weight Tolerant Subgraph for Single Source Shortest PathUnnamed ItemUnnamed Item




This page was built for publication: A nearly optimal oracle for avoiding failed vertices and edges