Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs

DOI10.1007/978-3-540-77050-3_27zbMath1135.90424OpenAlexW1606169264MaRDI QIDQ5458845

Telikepalli Kavitha

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Distributed distance computation and routing with small messages ⋮ \(f\)-sensitivity distance oracles and routing schemes

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

This page was built for publication: Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs