Premium
A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves
Author(s) -
Brazil M.,
Thomas D. A.,
Weng J. F.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199903)33:2<145::aid-net5>3.0.co;2-n
Subject(s) - steiner tree problem , disjoint sets , mathematics , time complexity , combinatorics , set (abstract data type) , algorithm , simple (philosophy) , polynomial , plane (geometry) , discrete mathematics , computer science , geometry , epistemology , programming language , mathematical analysis , philosophy
The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP‐complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectilinear Steiner problem for the case where terminals are constrained to lie on almost any fixed set of simple disjoint compact curves. © 1999 John Wiley & Sons, Inc. Networks 33: 145–155, 1999