Approximating the Diameter of Planar Graphs in Near Linear Time
classification
💻 cs.DS
keywords
diameterepsilonplanartimealgorithmapproximatingapproximationcdot
read the original abstract
We present a $(1+\epsilon)$-approximation algorithm running in $O(f(\epsilon)\cdot n \log^4 n)$ time for finding the diameter of an undirected planar graph with non-negative edge lengths.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.