The Steiner tree problem for terminals on the boundary of a rectilinear polygon

Authors
Cheng, SW
Citation
Sw. Cheng, The Steiner tree problem for terminals on the boundary of a rectilinear polygon, THEOR COMP, 237(1-2), 2000, pp. 213-238
Citations number
11
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
237
Issue
1-2
Year of publication
2000
Pages
213 - 238
Database
ISI
SICI code
0304-3975(20000428)237:1-2<213:TSTPFT>2.0.ZU;2-9
Abstract
Given a simple rectilinear polygon P with k sides and n terminals on its bo undary, we present an O(k(3)n)-time algorithm to compute the minimal rectil inear Steiner tree lying inside P interconnecting the terminals. We obtain our result by proving structural properties of a selective set of minimal S teiner trees and exploiting them in a dynamic programming algorithm. (C) 20 00 Elsevier Science B.V. All rights reserved.