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

DOI10.1007/978-3-540-77050-3_27MaRDI QIDQ5458845zbMATH OpenOpenAlexFDO

Authors 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) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Faster algorithms for all-pairs small stretch distances in weighted graphs
• Faster algorithms for all-pairs approximate shortest paths in undirected graphs
• All-pairs small-stretch paths
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• All-Pairs Almost Shortest Paths

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A new approach to all-pairs shortest paths on real-weighted graphs
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-Pairs Almost Shortest Paths
• All-pairs small-stretch paths
• Approximate distance oracles
• Computing almost shortest paths
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fast rectangular matrix multiplication and applications
• Faster algorithms for all-pairs small stretch distances in weighted graphs
• More algorithms for all-pairs shortest paths in weighted graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• STACS 2005

Cited in

(5)

• \(f\)-sensitivity distance oracles and routing schemes
• Distributed distance computation and routing with small messages
• All-pairs small-stretch paths
• Faster algorithms for all-pairs approximate shortest paths in undirected graphs
• Faster algorithms for all-pairs small stretch distances in weighted graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458845)