Approximating the Diameter of Planar Graphs in Near Linear Time

DOI10.1145/2764910zbMath1398.68686OpenAlexW1597730645MaRDI QIDQ4962209

Oren Weimann, Raphael Yuster

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2764910

zbMATH Keywords

diameterplanar graphsdistance oraclesall-pairs shortest paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)

Related Items (5)

Faster approximate diameter and distance oracles in planar graphs ⋮ Succinct enumeration of distant vertex pairs ⋮ Unnamed Item ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Parameterized complexity of diameter

This page was built for publication: Approximating the Diameter of Planar Graphs in Near Linear Time