A near linear time approximation scheme for Steiner tree among obstacles in the plane
From MaRDI portal
Publication:2269141
DOI10.1016/j.comgeo.2009.01.011zbMath1215.05189OpenAlexW2087083181WikidataQ57013199 ScholiaQ57013199MaRDI QIDQ2269141
Siamak Tazari, Matthias Müller-Hannemann
Publication date: 16 March 2010
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2009.01.011
Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Steiner problem with edge lengths 1 and 2
- The Steiner problem in phylogeny is NP-complete
- The Steiner tree problem
- Minimum Networks in Uniform Orientation Metrics
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
- An Approximation Scheme for Finding Steiner Trees with Obstacles
- On Steiner Minimal Trees with Rectilinear Distance
- Une heuristique pour le problème de l'arbre de Steiner
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The Complexity of Computing Steiner Minimal Trees
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Planar spanners and approximate shortest path queries among obstacles in the plane
- HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES
- On Steiner’s Problem with Rectilinear Distance
- Steiner Minimal Trees
- Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles
- Algorithms and Data Structures
This page was built for publication: A near linear time approximation scheme for Steiner tree among obstacles in the plane
