Optimal distributed algorithm for minimum spanning trees revisited

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal distributed algorithm for minimum spanning trees revisited

Full text

Pdf (847 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing table of contents

Ottowa, Ontario, Canada

Pages: 231 - 237

Year of Publication: 1995

ISBN:0-89791-710-3

Authors

Michalis Faloutsos	University of Toronto, Dpt. of Computer Science, Toronto M5S 1A4, Ontario, Canada
Mart Molle	University of Toronto and University of California at Riverside, Dept. of Computer Science, Riverside, CA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 25, Citation Count: 4

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/224964.225474 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.

	Awe87	B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
	CT85	F. Chin and H.F. Ting. An almost linear time and o(vlogv + e) messages distributed algorithm for minimum weight spanning trees. Proceedings of Foundations Of Computer Science (FOCS) Conference Portland, Oregon, October 1985.
	Fal95	Michalis Faloutsos. Corrections, improvements, simulations and optimstic algorithms for the distributed minimum spanning tree problem. Technical Report CSRI-316, 1995.
	FM95	Michalis Faloutsos and Mart MoHe. Creating optimal distributed algorithms for minimum spanning trees. Technical Report CSRI-327 (also submitted in WDA G '95), 1995.
	Gaf85	Eli Gafni, Improvements in the time complexity of two message-optimal election algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.175-185, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323612]
	GHS83	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	GKP93	J.A. Garay, S. Kutten, and D. Peleg. A sublinear time distributed algorithm for minimumweight spanning trees. Proceedings of Foundations Of Computer Science (FOCS), 34, 1993.
	SB95	Gurdip Singh , Arthur J. Bernstein, A highly asynchronous minimum spanning tree protocol, Distributed Computing, v.8 n.3, p.151-161, March 1995 [doi>10.1007/BF02242717]

CITED BY 4

	Michalis Faloutsos , Mart Molle, A linear-time optimal-message distributed algorithm for minimum spanning trees, Distributed Computing, v.17 n.2, p.151-170, August 2004
	Saurabh Srivastava , R. K. Ghosh, Cluster based routing using a k-tree core backbone for mobile ad hoc networks, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Alexandre O. Stauffer , Valmir C. Barbosa, Local heuristics and the emergence of spanning subgraphs in complex networks, Theoretical Computer Science, v.355 n.1, p.80-95, 6 April 2006
	Raghupathy Sivakumar , Bevan Das , Vaduvur Bharghavan, Spine routing in ad hoc networks, Cluster Computing, v.1 n.2, p.237-248, 1998