Faster Approximation of Distances in Graphs

DOI10.1007/978-3-540-73951-7_47zbMath1209.05238OpenAlexW1530560842MaRDI QIDQ3603556

Shiva Prasad Kasiviswanathan, Piotr Berman

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

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

Related Items (10)

Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Unnamed Item ⋮ All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fast approximate shortest paths in the congested clique ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs

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