\(f\)-sensitivity distance oracles and routing schemes
From MaRDI portal
Publication:692635
DOI10.1007/s00453-011-9543-0zbMath1254.68095OpenAlexW2766824301MaRDI QIDQ692635
Michael Langberg, Shiri Chechik, David Peleg, Liam Roditty
Publication date: 6 December 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9543-0
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Data structures (68P05) Reliability, testing and fault tolerance of networks and computer systems (68M15)
Related Items
The impact of dynamic events on the number of errors in networks ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Compact routing messages in self-healing trees ⋮ Vertex fault tolerant additive spanners ⋮ Compact distance oracles with large sensitivity and low stretch ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Unnamed Item ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Feasibility and complexity of broadcasting with random transmission failures
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Compact Routing with Minimum Stretch
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Experimental analysis of dynamic all pairs shortest path algorithms
- Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs
- Slide—The Key to Polynomial End-to-End Communication
- Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures
- Improved routing strategies with succinct tables
- Oracles for Distances Avoiding a Failed Node or Link
- Approximate distance oracles
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Worst-case update times for fully-dynamic all-pairs shortest paths
- Compact Forbidden-Set Routing
- The Byzantine generals strike again
- Almost Safe Gossiping in Bounded Degree Networks
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- The impossibility of implementing reliable communication in the face of crashes
- Optimal communication in networks with randomly distributed byzantine faults
- Sparsification—a technique for speeding up dynamic graph algorithms
- Information dissemination in distributed systems with faulty units
- Distributed Computing: A Locality-Sensitive Approach
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Compact routing schemes with low stretch factor
- All-Pairs Almost Shortest Paths
- A nearly optimal oracle for avoiding failed vertices and edges
- Algorithm Theory - SWAT 2004
- Memory requirement for universal routing schemes
- Fault Tolerant Spanners for General Graphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
- Fault-tolerant broadcasting and gossiping in communication networks
- Automata, Languages and Programming
- Computing almost shortest paths
- Space-efficiency for routing schemes of stretch factor three
