Approximating the diameter of planar graphs in near linear time

DOI10.1007/978-3-642-39206-1_70MaRDI QIDQ5326614zbMATH OpenOpenAlexFDO

Authors Oren Weimann, Raphael Yuster

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1116

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: We present a $(1+epsilon)$-approximation algorithm running in $O(f(epsilon)cdotnlo{g}^{4}n)$ time for finding the diameter of an undirected planar graph with non-negative edge lengths.

Recommendations

• Approximating the Diameter of Planar Graphs in Near Linear Time
• Faster approximate diameter and distance oracles in planar graphs
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Cited in

(17)

• scientific article; zbMATH DE number 5050599 (Why is no real title available?)
• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• scientific article; zbMATH DE number 7561539 (Why is no real title available?)
• Planar diameter via metric compression
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Computing the Girth of a Planar Graph in O(n logn) Time
• Faster approximate diameter and distance oracles in planar graphs
• On Approximating the d-Girth of a Graph
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Complexity of approximating the oriented diameter of chordal graphs
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Approximation algorithms for min-distance problems in DAGs
• Diameter bounds for planar graphs
• Computing giant graph diameters
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Fast and Simple Approximation of the Diameter and Radius of a Graph

This page was built for publication: Approximating the diameter of planar graphs in near linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326614)