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 (13)
- 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
- Title not available (Why is that?)
- Optimal Surface Flattening
- Counting and sampling minimum cuts in genus \(g\) graphs
- 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
- Title not available (Why is that?)
- Minimum Cuts in Surface 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)
