RECTILINEAR SHORTEST PATHS AND MINIMUM SPANNING-TREES IN THE PRESENCE OF RECTILINEAR OBSTACLES

被引：64
作者：
WU, YF
WIDMAYER, P
SCHLAG, MDF
WONG, CK
机构：
[1] NORTHWESTERN UNIV,DEPT ELECT ENGN & COMP SCI,EVANSTON,IL 60201
[2] IBM CORP,THOMAS J WATSON RES CTR,YORKTOWN HTS,NY 10598
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1987年 / 36卷 / 03期
关键词：
D O I：
10.1109/TC.1987.1676904
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
引用
收藏
页码：321 / 331
页数：11
相关论文
共 50 条
[21]   An Exact Algorithm for the Construction of Rectilinear Steiner Minimum Trees Among Complex Obstacles [J].
Huang, Tao ;
Young, Evangeline F. Y. .
PROCEEDINGS OF THE 48TH ACM/EDAC/IEEE DESIGN AUTOMATION CONFERENCE (DAC), 2011, :164-169
[22]   Rectilinear spanning trees versus bounding boxes [J].
Rautenbach, D .
ELECTRONIC JOURNAL OF COMBINATORICS, 2004, 11 (01)
[23]   An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains [J].
Joseph S. B. Mitchell ;
Valentin Polishchuk ;
Mikko Sysikaski ;
Haitao Wang .
Algorithmica, 2019, 81 :289-316
[24]   An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains [J].
Mitchell, Joseph S. B. ;
Polishchuk, Valentin ;
Sysikaski, Mikko ;
Wang, Haitao .
AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2015, 9134 :947-959
[25]   An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains [J].
Mitchell, Joseph S. B. ;
Polishchuk, Valentin ;
Sysikaski, Mikko ;
Wang, Haitao .
ALGORITHMICA, 2019, 81 (01) :289-316
[26]   ON RANDOM MINIMUM LENGTH SPANNING-TREES [J].
FRIEZE, AM ;
MCDIARMID, CJH .
COMBINATORICA, 1989, 9 (04) :363-374
[27]   ON MINIMUM SPANNING-TREES AND THE INTERGRADATION OF CLUSTERS [J].
WARSHAUER, SM ;
SMOSNA, R .
JOURNAL OF THE INTERNATIONAL ASSOCIATION FOR MATHEMATICAL GEOLOGY, 1981, 13 (03) :225-235
[28]   TRANSITIONS IN GEOMETRIC MINIMUM SPANNING-TREES [J].
MONMA, C ;
SURI, S .
DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 8 (03) :265-293
[29]   Trans-dichotomous algorithms for minimum spanning trees and shortest paths [J].
Fredman, Michael L., 1600, Academic Press Inc, San Diego, CA, United States (48)
[30]   Shortest path queries among weighted obstacles in the rectilinear plane [J].
Chen, DZ ;
Klenk, KS ;
Tu, HYT .
SIAM JOURNAL ON COMPUTING, 2000, 29 (04) :1223-1246
12345