Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
From MaRDI portal
Publication:5458845
DOI10.1007/978-3-540-77050-3_27zbMath1135.90424MaRDI QIDQ5458845
Publication date: 24 April 2008
Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://eprints.iisc.ac.in/41497/1/10.1.1.100.8606.pdf
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
\(f\)-sensitivity distance oracles and routing schemes, Distributed distance computation and routing with small messages
Cites Work
- Unnamed Item
- Fast rectangular matrix multiplication and applications
- A new approach to all-pairs shortest paths on real-weighted graphs
- Faster algorithms for all-pairs small stretch distances in weighted graphs
- All-Pairs Small-Stretch Paths
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Approximate distance oracles
- More algorithms for all-pairs shortest paths in weighted graphs
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- All-Pairs Almost Shortest Paths
- STACS 2005
- Computing almost shortest paths
