Approximating Shortest Paths in Graphs
From MaRDI portal
Publication:3605483
DOI10.1007/978-3-642-00202-1_3zbMath1211.68292OpenAlexW1581228220MaRDI QIDQ3605483
Publication date: 24 February 2009
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A parallel bio-inspired shortest path algorithm, Shortest-path queries in static networks, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- On sparse spanners of weighted graphs
- A new approach to all-pairs shortest paths on real-weighted graphs
- All-Pairs Small-Stretch Paths
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- More algorithms for all-pairs shortest paths in weighted graphs
- Spanners and emulators with sublinear distance errors
- Complexity of network synchronization
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Graph spanners
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- All-Pairs Almost Shortest Paths
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- STACS 2005
- Automata, Languages and Programming
- Computing almost shortest paths
