An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees

Full text

Pdf (329 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 2 (April 1979) table of contents

Pages: 177 - 182

Year of Publication: 1979

ISSN:0004-5411

Author

F. K. Hwang

Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 50, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322123.322124 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	BORUVKA, O On a mmtmal problem Prace Morask~ Pndovedeckd Spolecnostl, Vol 3, 1926
	3	CHERITON. R, AND TARJAN, R E Finding minimum spanning trees SlAM J Comptng 5 (Dec 1976), 724- 742
	4	CHOQUET, G Etude de certalns reseaux de routes C R Acad Sct Parts 206 (1938), 310--313
	5	KRUSKAL, J B On the shortest spanning subtree of a graph. Proc. Amer Math. Soc 7 (Feb 1956), 48-50
	6	PRIM, R C Shortest connecting networks and some generahzatlons Bell Syst Tech J 36 (Nov 1957), 1389- 1401
	7	SnAMOS, M. I., AND HOEV, D Closest pomt problems Proc 16th Annual Symp Foundations of Comptr Sct., 1975, pp 151-162 (avadable from IEEE, New York)

CITED BY 20

	Weiping Shi , Chen Su, The rectilinear Steiner arborescence problem is NP-complete, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.780-787, January 09-11, 2000, San Francisco, California, United States
	Robert L. (Scot) Drysdale, III, A practical algorithm for computing the Delaunay triangulation for convex distance functions, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.159-168, January 22-24, 1990, San Francisco, California, United States
	Jan-ming Ho , G. Vijayan , C. K. Wong, A new approach to the rectilinear Steiner tree problem, Proceedings of the 26th ACM/IEEE conference on Design automation, p.161-166, June 25-28, 1989, Las Vegas, Nevada, United States
	D. T. Lee, Two-Dimensional Voronoi Diagrams in the Lp-Metric, Journal of the ACM (JACM), v.27 n.4, p.604-618, Oct. 1980
	Evagelos Katsadas , Edwin Kinnen, A multi-layer router utilizing over-cell areas, Proceedings of the 27th ACM/IEEE conference on Design automation, p.704-708, June 24-27, 1990, Orlando, Florida, United States
	William Swartz , Carl Sechen, A new generalized row-based global router, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.491-498, November 07-11, 1993, Santa Clara, California, United States
	Hai Zhou , Narendra Shenoy , William Nicholls, Efficient minimum spanning tree construction without Delaunay triangulation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.192-197, January 2001, Yokohama, Japan
	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	Moses Charikar , Dan Halperin , Rajeev Motwani, The dynamic servers problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.410-419, January 25-27, 1998, San Francisco, California, United States
	M. Sarrafzadeh , C. K. Wong, Bottleneck Steiner Trees in the Plane, IEEE Transactions on Computers, v.41 n.3, p.370-374, March 1992
	P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States
	Hai Zhou, Efficient Steiner tree construction based on spanning graphs, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	R A Dwyer, A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time, Proceedings of the second annual symposium on Computational geometry, p.276-284, June 02-04, 1986, Yorktown Heights, New York, United States
	Yung H. Tsin , Cao-An Wang, Geodesic Voronoi diagrams in the presence of rectilinear barriers, Nordic Journal of Computing, v.3 n.1, p.1-26, Spring 1996
	Alexander Z. Zelikovsky , Ion I. Măndoiu, Practical approximation algorithms for zero- and bounded-skew trees, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.407-416, January 07-09, 2001, Washington, D.C., United States
	Qi Zhu , Hai Zhou , Tong Jing , Xianlong Hong , Yang Yang, Efficient octilinear Steiner tree construction based on spanning graphs, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.687-690, January 27-30, 2004, Yokohama, Japan
	P. Widmayer , Y. F. Wu , C. K. Wong, Distance problems in computational geometry with fixed orientations, Proceedings of the first annual symposium on Computational geometry, p.186-195, June 05-07, 1985, Baltimore, Maryland, United States
	L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States
	Chunhong Chen, Probabilistic Analysis of Rectilinear Steiner Trees, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.484, January 07-11, 2002