Efficient minimum spanning tree construction without Delaunay triangulation
作者： Hai Zhou , Narendra Shenoy , William Nicholls
DOI: 10.1016/S0020-0190(01)00232-0
关键词:
摘要: … spanning tree problem is a very important problem in VLSI CAD. Given n points in a plane, a minimum spanning tree is a … More efficient approaches find a minimum spanning tree only …
acm.org
elsevier.com
sci-hub.se 参考文章(12)
Gary M. Shute, Linda L. Deneen, Clark D. Thomborson, AnO(n logn) plane-sweep algorithm forL1 andLź Delaunay triangulations Algorithmica. ,vol. 6, pp. 207- 221 ,(1991) , 10.1007/BF01759042
Leo J. Guibas, Jorge Stolfi, On computing all north-east nearest neighbors in the L1 metric Information Processing Letters. ,vol. 17, pp. 219- 223 ,(1983) , 10.1016/0020-0190(83)90045-5
Andrew Chi-Chih Yao, On constructing minimum spanning trees in k-dimensional spaces and related problems SIAM Journal on Computing. ,vol. 11, pp. 721- 736 ,(1977) , 10.1137/0211059
F. K. Hwang, An
O
(
n
log
n
) Algorithm for Rectilinear Minimal Spanning Trees Journal of the ACM. ,vol. 26, pp. 177- 182 ,(1979) , 10.1145/322123.322124
G. Robins, J. S. Salowe, Low-degree minimum spanning trees Discrete and Computational Geometry. ,vol. 14, pp. 151- 165 ,(1995) , 10.1007/BF02570700
Steven Fortune, A sweepline algorithm for Voronoi diagrams Algorithmica. ,vol. 2, pp. 153- 174 ,(1987) , 10.1007/BF01840357
William Pugh, Skip lists: a probabilistic alternative to balanced trees Communications of the ACM. ,vol. 33, pp. 668- 676 ,(1990) , 10.1145/78973.78977
Eugene L. Lawler, Combinatorial optimization : networks and matroids Dover Publications. ,(1976)
S.Q. Zheng, Joon Shink Lim, S.S. Iyengar, Finding obstacle-avoiding shortest paths using implicit connection graphs IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 15, pp. 103- 110 ,(1996) , 10.1109/43.486276
Edward M. McCreight, Priority Search Trees SIAM Journal on Computing. ,vol. 14, pp. 257- 276 ,(1985) , 10.1137/0214021