Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon

DOI10.1007/978-3-540-73951-7_25MaRDI QIDQ3603533zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cited in

(17)

• Optimal Surface Flattening
• Counting and sampling minimum cuts in genus \(g\) graphs
• A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
• Flattening topologically spherical surface
• An \(O(n\log n)\) approximation scheme for Steiner tree in planar graphs
• Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
• 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
• Global minimum cuts in surface embedded graphs
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• Faster exact algorithms for steiner trees in planar networks
• Minimum Cuts in Surface Graphs
• A polynomial-time approximation scheme for planar multiway cut
• A dynamic programming approach for the pipe network layout problem
• A near linear time approximation scheme for Steiner tree among obstacles in the plane
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Dealing with large hidden constants: engineering a planar Steiner tree PTAS

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)