Faster Approximation of Distances in Graphs

DOI10.1007/978-3-540-73951-7_47zbMATH Open1209.05238OpenAlexW1530560842MaRDI QIDQ3603556FDOQ3603556

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

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

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)

Cited In (19)

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