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

DOI10.1007/978-3-540-73951-7_25zbMath1209.68633OpenAlexW1572973141MaRDI QIDQ3603533

Claire Mathieu, Glencora Borradaile, 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) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

Minimum Cuts in Surface Graphs ⋮ Optimal Surface Flattening ⋮ Flattening topologically spherical surface ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ A dynamic programming approach for the pipe network layout problem ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon