An Approximation Scheme for Finding Steiner Trees with Obstacles

DOI10.1137/0217057zbMath0665.68053OpenAlexW2071945466MaRDI QIDQ3816989

J. Scott Provan

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217057

zbMATH Keywords

convex hullSteiner minimal treeapproximation scheme

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (14)

An exact algorithm for constructing minimum Euclidean skeletons of polygons ⋮ HARDNESS AND APPROXIMATION OF OCTILINEAR STEINER TREES ⋮ Short trees in polygons ⋮ Shortest enclosing walks and cycles in embedded graphs ⋮ Simplifying obstacles for Steiner network problems in the plane ⋮ Polynomially solvable special cases of the Steiner problem in planar networks ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ Steiner minimal trees for three points with one convex polygonal obstacle ⋮ On the structure and complexity of the 2-connected Steiner network problem in the plane ⋮ Two new criteria for finding Steiner hulls in Steiner tree problems ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ The Steiner problem on surfaces of revolution ⋮ Local search for the Steiner tree problem in the Euclidean plane ⋮ Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs

This page was built for publication: An Approximation Scheme for Finding Steiner Trees with Obstacles