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

We give an O(n log3 n) approximation scheme for Steiner forest in planar graphs, improving on the previous approximation scheme for this problem, which runs in O(nf(e)) time.

• Publication year

  2011

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2011-10-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973099.53arXiv 1110.1320
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Steiner Forest Problem revisited

  2010cited by this paper
• An O(n log n) approximation scheme for Steiner tree in planar graphs

  2009cited by this paper
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

  2009cited by this paper
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

  2008cited by this paper
• A polynomial-time approximation scheme for Steiner tree in planar graphs

  2007cited by this paper
• Approximation algorithms via contraction decomposition

  2007cited by this paper
• Algorithmic graph minor theory: Decomposition, approximation, and coloring

  2005cited by this paper
• A linear-time approximation scheme for planar weighted TSP

  2005cited by this paper
• Fast 3-coloring Triangle-Free Planar Graphs

  2004cited by this paper
• On the approximability of the Steiner tree problem

  2003cited by this paper
• Dynamic Representation of Sparse Graphs

  1999cited by this paper
• A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm

  1994cited by this paper
• A general approximation technique for constrained forest problems

  1992cited by this paper
• When trees collide: an approximation algorithm for the generalized Steiner problem on networks

  1991cited by this paper
• The Steiner Problem with Edge Lengths 1 and 2

  1989cited by this paper

• Metric Sketching and Dynamic Algorithms for Geometric and Topological Graphs (Dagstuhl Seminar 25212)

  2025cites this paper
• Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications

  2024cites this paper
• Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

  2024influential citation
• A Framework for Approximation Schemes on Disk Graphs

  2022cites this paper
• On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

  2020cites this paper
• Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs

  2020cites this paper
• A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane

  2020cites this paper
• Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces

  2019influential citation
• An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs

  2019cites this paper
• PTAS for Steiner Tree on Map Graphs

  2019cites this paper
• Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs

  2019cites this paper
• Parameterized Computational Geometry via Decomposition Theorems

  2019cites this paper
• Algorithms above the noise floor

  2018cites this paper
• Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes

  2018cites this paper
• Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs

  2018cites this paper
• Excluded Grid Minors and EPTAS

  2018cites this paper
• On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs

  2017cites this paper
• Simultaneously Load Balancing for Every p-norm, With Reassignments

  2017cites this paper
• Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

  2017cites this paper
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

  2017cites this paper
• A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs

  2017cites this paper
• A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting

  2016influential citation
• Local-on-Average Distributed Tasks

  2016cites this paper
• Fast Algorithms for Structured Sparsity (ICALP 2015 Invited Tutorial)

  2015cites this paper
• A Nearly-Linear Time Framework for Graph-Structured Sparsity

  2015cites this paper
• FULLY DYNAMIC GRAPH ORIENTATION

  2015cites this paper
• Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

  2014cites this paper
• Toward Practical Planar Graph Algorithms

  2014cites this paper
• Directed Graphs: Fixed-Parameter Tractability & Beyond

  2014cites this paper
• Orienting Fully Dynamic Graphs with Worst-Case Time Bounds

  2013cites this paper
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

  2013cites this paper
• Characterisations of Nowhere Dense Graphs

  2013cites this paper
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs

  2013cites this paper