A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves

Authors
Brazil, M Thomas, DA Weng, JF
Citation
M. Brazil et al., A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves, NETWORKS, 33(2), 1999, pp. 145-155
Citations number
9
Categorie Soggetti
Computer Science & Engineering
Journal title
NETWORKS
ISSN journal
00283045 → ACNP
Volume
33
Issue
2
Year of publication
1999
Pages
145 - 155
Database
ISI
SICI code
0028-3045(199903)33:2<145:APTAFR>2.0.ZU;2-1
Abstract
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 rectili near Steiner problem for the case where terminals are constrained to lie on almost any fixed set of simple disjoint compact curves. (C) 1999 John Wile y & Sons, Inc.