A minimum spanning tree algorithm with inverse-Ackermann type complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A minimum spanning tree algorithm with inverse-Ackermann type complexity

Full text

Pdf (153 KB)

Source

Journal of the ACM (JACM) archive
Volume 47 , Issue 6 (November 2000) table of contents

Pages: 1028 - 1047

Year of Publication: 2000

ISSN:0004-5411

Author

Bernard Chazelle

Princeton Univ., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 30, Downloads (12 Months): 349, Citation Count: 23

Additional Information:

abstract references cited by index terms review collaborative colleagues peer to peer

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/355541.355562 What is a DOI?

ABSTRACT

A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is 0(m &agr;(m, n)), where &agr; is the classical functional inverse of Ackermann's function and n (respectively, m) is the number of vertices (respectively, edges). The algorithm is comparison-based : it uses pointers, not arrays, and it makes no numeric assumptions on the edge costs.

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	BORUVKA, O. 1926. O jistem problemu minimalnim. Prace Moravske Prirodovedecke Spolecnosti 3, 37-58 (in Czech).
	2	Bernard Chazelle, The soft heap: an approximate priority queue with optimal error rate, Journal of the ACM (JACM), v.47 n.6, p.1012-1027, Nov. 2000 [doi>10.1145/355541.355554]
	3	CHAZELLE, B., AND ROSENBERG, B. 1991. The complexity of computing partial sums off-line. Int. J. Comput. Geom. Appl. 1, 33-45.
	4	CHERITON, D., AND TARJAN, R. E. 1976. Finding minimum spanning trees, SIAM J. Comput. 5, 724-742.
	5	Brandon Dixon , Monika Rauch , Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing, v.21 n.6, p.1184-1192, Dec. 1992 [doi>10.1137/0221070]
	6	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	7	Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
	8	H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
	9	GRAHAM, R. L., AND HELL, P. 1985. On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7, 43-57.
	10	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
	11	KING, V. 1997. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263-270.
	12	KOMLOS, J. 1983. Linear verification for spanning trees. Combinatorica 5, 57-65.
	13	NESETRIL, J. 1997. A few remarks on the history of MST-problem. Arch. Math. Brno 33, 15-22.
	14	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	15	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	16	TARJAN, R. E. 1978. Complexity of monotone networks for computing conjunctions. Ann. Disc. Math. 2, 121-133.
	17	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	18	YAO, A. 1975. An O(u Eu log logu Vu ) algorithm for finding minimum spanning trees. Inf. Process. Lett. 4, 21-23.

CITED BY 23

	Sanguthevar Rajasekaran, Efficient Parallel Hierarchical Clustering Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.497-502, June 2005
	Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Mariano Zelke, Optimal per-edge processing times in the semi-streaming model, Information Processing Letters, v.104 n.3, p.106-112, October, 2007
	Bernard Chazelle, The soft heap: an approximate priority queue with optimal error rate, Journal of the ACM (JACM), v.47 n.6, p.1012-1027, Nov. 2000
	Mikkel Thorup, Combinatorial power in multimedia processors, ACM SIGARCH Computer Architecture News, v.31 n.4, p.5-11, Sept 2003
	Artur Czumaj , Christian Sohler, Testing Euclidean minimum spanning trees in the plane, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-23, June 2008
	Seth Pettie, A new approach to all-pairs shortest paths on real-weighted graphs, Theoretical Computer Science, v.312 n.1, p.47-74, 26 January 2004
	Haim Kaplan , Uri Zwick, A simpler implementation and analysis of Chazelle's soft heaps, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.477-485, January 04-06, 2009, New York, New York
	Ka Wong Chong , Yijie Han , Tak Wah Lam, Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM (JACM), v.48 n.2, p.297-323, March 2001
	Artur Czumaj , Christian Sohler, Estimating the weight of metric minimum spanning trees in sublinear-time, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Michel X. Goemans , Jan Vondrák, Covering minimum spanning trees of random subgraphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Piotr Juszczak , David M. J. Tax , Elbieta Pekalska , Robert P. W. Duin, Minimum spanning tree based one-class classifier, Neurocomputing, v.72 n.7-9, p.1859-1869, March, 2009
	Seth Pettie , Vijaya Ramachandran, Computing shortest paths with comparisons and additions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.267-276, January 06-08, 2002, San Francisco, California
	Seth Pettie , Vijaya Ramachandran, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.713-722, January 06-08, 2002, San Francisco, California
	Ran Mendelson , Robert E. Tarjan , Mikkel Thorup , Uri Zwick, Melding priority queues, ACM Transactions on Algorithms (TALG), v.2 n.4, p.535-556, October 2006
	Tzu-Chiang Chiang , Chien-Hung Liu , Yueh-Min Huang, A near-optimal multicast scheme for mobile ad hoc networks using a hybrid genetic algorithm, Expert Systems with Applications: An International Journal, v.33 n.3, p.734-742, October, 2007
	Seth Pettie , Vijaya Ramachandran, Randomized minimum spanning tree algorithms using exponentially fewer random bits, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-27, March 2008
	Seth Pettie , Vijaya Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), v.49 n.1, p.16-34, January 2002
	Ran Mendelson , Mikkel Thorup , Uri Zwick, Meldable RAM priority queues and minimum directed spanning trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	David Eppstein , Michael T. Goodrich , Darren Strash, Linear-time algorithms for geometric graphs with sublinearly many crossings, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.150-159, January 04-06, 2009, New York, New York
	Sarah Steiner , Tomasz Radzik, Computing all efficient solutions of the biobjective minimum spanning tree problem, Computers and Operations Research, v.35 n.1, p.198-211, January, 2008
	Mikkel Thorup, On AC⁰ implementations of fusion trees and atomic heaps, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Gustavo B. Figueiredo , Nelson L. S. da Fonseca , José A. S. Monteiro, A minimum interference routing algorithm with reduced computational complexity, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.11, p.1710-1732, 10 August 2006

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory

Keywords:
graphs, matroids, minimum spanning trees

REVIEW

"Paul Cull : Reviewer"

An old chestnut has almost been shelled. Finding the minimum spanning tree is a basic problem which figures as an example in most graph and algorithm texts. The traditional algorithms have 0(E by E) run time. Usually a student will ask wheth more...

Collaborative Colleagues:

Bernard Chazelle: colleagues

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player