Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
From MaRDI portal
Publication:4575887
DOI10.1137/1.9781611974782.139zbMath1403.68151OpenAlexW2952702960MaRDI QIDQ4575887
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611974782.139
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs, Unnamed Item, Unnamed Item, Faster approximate diameter and distance oracles in planar graphs, The inverse Voronoi problem in graphs. I: Hardness, An efficient oracle for counting shortest paths in planar graphs, Unnamed Item, Fast approximation of eccentricities and distances in hyperbolic graphs, Faster Approximate Diameter and Distance Oracles in Planar Graphs, An efficient oracle for counting shortest paths in planar graphs, An efficient noisy binary search in graphs via Median approximation
