ALGORITHMS FOR SPECIAL CASES OF RECTILINEAR STEINER TREES .1. POINTS ON THE BOUNDARY OF A RECTILINEAR RECTANGLE

被引：10

作者：

AGARWAL, PK ^{[1
]}

SHING, MT ^{[1
]}

机构：

[1] USN,POSTGRAD SCH,DEPT COMP SCI,MONTEREY,CA 93943

来源：

NETWORKS | 1990年 / 20卷 / 04期

关键词：

D O I：

10.1002/net.3230200407

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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

引用

页码：453 / 485

页数：33

共 10 条

[1]

AGARWAL PK, 1986, ALGORITHMS SPECIAL C, V1

[2] RECTILINEAR STEINER TREES - EFFICIENT SPECIAL-CASE ALGORITHMS [J].