Oracles for Distances Avoiding a Failed Node or Link
From MaRDI portal
Publication:3532564
DOI10.1137/S0097539705429847zbMath1158.05057WikidataQ30000105 ScholiaQ30000105MaRDI QIDQ3532564
Vijaya Ramachandran, Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury
Publication date: 28 October 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Communication networks in operations research (90B18) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20) General topics in the theory of algorithms (68W01)
Related Items (25)
The impact of dynamic events on the number of errors in networks ⋮ On resilient graph 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 ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Unnamed Item ⋮ Compact distance oracles with large sensitivity and low stretch ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ 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 ⋮ Unnamed Item ⋮ Fault-tolerant approximate shortest-path trees ⋮ Resilient capacity-aware routing ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Incremental distance products via faulty shortest paths ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Unnamed Item
This page was built for publication: Oracles for Distances Avoiding a Failed Node or Link
