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)

• A polynomial-time approximation scheme for planar multiway cut
• A dynamic programming approach for the pipe network layout problem
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• 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
• Counting and sampling minimum cuts in genus g graphs
• Optimal Surface Flattening
• 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
• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
• Minimum Cuts in Surface Graphs
• An O(n n) approximation scheme for Steiner tree in planar graphs
• Global minimum cuts in surface embedded graphs

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)