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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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): 4, 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