Faster Approximation of Distances in Graphs

DOI10.1007/978-3-540-73951-7_47MaRDI QIDQ3603556zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Shiva Prasad Kasiviswanathan

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_47

zbMATH Keywords

deterministic algorithmBoolean matrix multiplicationdiameter of a graphweighted undirected graphradius of a graphshortest path metric

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Distance in graphs (05C12) Signed and weighted graphs (05C22)

Recommendations

• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fast and Simple Approximation of the Diameter and Radius of a Graph
• Fast approximation algorithms for the diameter and radius of sparse graphs
• STACS 2005
• Better approximation algorithms for the graph diameter

Cited in

(19)

• A fast algorithm for connectivity graph approximation using modified Manhattan distance in dynamic networks
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• scientific article; zbMATH DE number 2119743 (Why is no real title available?)
• Efficient approximation algorithms for shortest cycles in undirected graphs
• All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
• New algorithms for all pairs approximate shortest paths
• scientific article; zbMATH DE number 7561539 (Why is no real title available?)
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Fast algorithms for approximating distances
• Some results on approximate 1-median selection in metric spaces
• Efficient Point-to-Point Resistance Distance Queries in Large Graphs
• Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
• A comparison of three algorithms for approximating the distance distribution in real-world graphs
• Fast and Simple Approximation of the Diameter and Radius of a Graph
• STACS 2005
• Fast approximate shortest paths in the congested clique
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Faster approximate diameter and distance oracles in planar graphs
• Approximate Distance Queries in Disk Graphs

This page was built for publication: Faster Approximation of Distances in Graphs

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