Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle


Journal Article

The general rectilinear Steiner tree problem has been proved to be NPÔÇÉcomplete. In this paper, we consider a special case in which the points lie on the boundary of a rectilinear rectangle and give an O(n) algorithm to construct a minimum rectilinear Steiner tree for such points. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Shing, M

Published Date

  • January 1, 1990

Published In

Volume / Issue

  • 20 / 4

Start / End Page

  • 453 - 485

Electronic International Standard Serial Number (EISSN)

  • 1097-0037

International Standard Serial Number (ISSN)

  • 0028-3045

Digital Object Identifier (DOI)

  • 10.1002/net.3230200407

Citation Source

  • Scopus