An efficient polynomial-time approximation scheme for Steiner forest in planar graphs

2011/10/06 by David D. Eisenstat, Eisenstat, David, Philip Α. Klein +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1110.1320

openalex publication_date 2011/10/06 · openalex created_date 2022/09/22 · openalex updated_date 2026/07/28

Abstract

We give an O(n log³ n) approximation scheme for Steiner forest in planar graphs, improving on the previous approximation scheme for this problem, which runs in O(n^f(ε)) time.

Cited by

• Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

Related

• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Prize-Collecting Steiner Tree and Forest in Planar Graphs
• A polynomial-time approximation scheme for Euclidean Steiner forest
• Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
• An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs