All-pairs nearly 2-approximate shortest paths in O(n^2 polylog n) time

DOI10.1016/J.TCS.2008.10.018MaRDI QIDQ1001904zbMATH OpenOpenAlexFDO

Authors Surender Baswana, Vishrut Goyal, Sandeep Sen

Publication date 19 February 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.10.018

zbMATH Keywords

distanceshortest pathspanner

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• STACS 2005
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• All-Pairs Almost Shortest Paths
• All-pairs shortest paths in \(O(n^2)\) time with high probability

Cites work

• 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
• Automata, Languages and Programming
• 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)
• Faster Approximation of Distances in Graphs
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• scientific article; zbMATH DE number 6469155 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• More algorithms for all-pairs shortest paths in weighted graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On the exponent of all pairs shortest path problem
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Subcubic cost algorithms for the all pairs shortest path problem

Cited in

(18)

• A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Approximating Shortest Paths in Graphs
• Some results on approximate 1-median selection in metric spaces
• All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
• scientific article; zbMATH DE number 6861957 (Why is no real title available?)
• scientific article; zbMATH DE number 219247 (Why is no real title available?)
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• scientific article; zbMATH DE number 913360 (Why is no real title available?)
• All-Pairs Almost Shortest Paths
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• STACS 2005
• New algorithms for all pairs approximate shortest paths
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• On the space usage of approximate distance oracles with sub-2 stretch
• New tradeoffs for decremental approximate all-pairs shortest paths
• New tradeoffs for decremental approximate all-pairs shortest paths
• On the all-pairs-shortest-path problem in unweighted undirected graphs.

This page was built for publication: All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time

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