A near linear time approximation scheme for Steiner tree among obstacles in the plane

DOI10.1016/J.COMGEO.2009.01.011MaRDI QIDQ2269141zbMATH OpenOpenAlexWikidataFDO

Authors 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

zbMATH Keywords

obstaclesplanar graphspannerEuclidean metricSteiner treePTASbanyanuniform orientation metric

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• An approximation scheme for some Steiner tree problems in the plane
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• scientific article; zbMATH DE number 1555959

Cites work

• scientific article; zbMATH DE number 6381762 (Why is no real title available?)
• scientific article; zbMATH DE number 3717342 (Why is no real title available?)
• scientific article; zbMATH DE number 1947438 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 750011 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 970831 (Why is no real title available?)
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles
• Approximation of rectilinear Steiner trees with length restrictions on obstacles.
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES
• Minimum networks in uniform orientation metrics
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner’s Problem with Rectilinear Distance
• Planar spanners and approximate shortest path queries among obstacles in the plane
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Steiner Minimal Trees
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• The Complexity of Computing Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Steiner problem in phylogeny is NP-complete
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• Une heuristique pour le problème de l'arbre de Steiner

Cited in

(10)

• An exact algorithm for constructing minimum Euclidean skeletons of polygons
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane
• scientific article; zbMATH DE number 1985307 (Why is no real title available?)
• Dealing with large hidden constants: engineering a planar Steiner tree PTAS
• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Approximation algorithms for network design problems
• An O(n n) approximation scheme for Steiner tree in planar graphs
• A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon

This page was built for publication: A near linear time approximation scheme for Steiner tree among obstacles in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2269141)