Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
DOI10.1007/978-3-540-73951-7_25zbMATH Open1209.68633OpenAlexW1572973141MaRDI QIDQ3603533FDOQ3603533
Authors: Glencora Borradaile, Claire Mathieu, Philip N. Klein 
Publication date: 17 February 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73951-7_25
Recommendations
- Faster exact algorithms for steiner trees in planar networks
- A faster approximation algorithm for the Steiner problem in graphs
- An approximation scheme for some Steiner tree problems in the plane
- A near linear time approximation scheme for Steiner tree among obstacles in the plane
- A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cited In (17)
- Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
- A dynamic programming approach for the pipe network layout problem
- An O ( n log n ) approximation scheme for Steiner tree in planar graphs
- Faster exact algorithms for steiner trees in planar networks
- Flattening topologically spherical surface
- A near linear time approximation scheme for Steiner tree among obstacles in the plane
- A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
- Dealing with large hidden constants: engineering a planar Steiner tree PTAS
- Optimal Surface Flattening
- Counting and sampling minimum cuts in genus \(g\) graphs
- Dealing with large hidden constants, engineering a planar Steiner tree PTAS
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
- Minimum Cuts in Surface Graphs
- Global minimum cuts in surface embedded graphs
- A polynomial-time approximation scheme for planar multiway cut
This page was built for publication: Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603533)
