A Distributed Algorithm for Minimum-Weight Spanning Trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Distributed Algorithm for Minimum-Weight Spanning Trees

Full text

Pdf (763 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 5 , Issue 1 (January 1983) table of contents

Pages: 66 - 77

Year of Publication: 1983

ISSN:0164-0925

Authors

R. G. Gallager	Room 35-206, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA
P. A. Humblet	Room 35-203, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA
P. M. Spira	Apple Computer Company, 10260 Bandley Drive, Cupertino, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 50, Downloads (12 Months): 305, Citation Count: 124

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/357195.357200 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	DALAL, Y. Broadcast protocols in packet switched computer networks. Tech. Rep. 128, Dep. of Electrical Engineering, Stanford Univ., Apr. 1977 (revised version for publication in preparation).
	2	DIJKSTRA, E. Two problems in connection with graphs. Numer. Math. I (1959), 269-271.
	3	HUMBLET, P.A. A distributed algorithm for minimum weight directed spanning trees. Rep. LIDS-P-1149, Laboratory for Information and Decision Systems, Massachusetts Inst. of Technology, Cambridge, Mass., Sept. 1981.
	4	KRUSKAL, J.B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7 (1956), 48-50.
	5	LAWLER, E. Combinatorial Optimization-Networks and Matroids. Holt, Rinehart & Winston, New York, 1976.
	6	LIU, C.L. Introduction to Combinatorial Mathematics. McGraw Hill, New York, 1968.
	7	PRIM, R.C. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36 (1957), 1389-1401.
	8	SPmA, P. Communication complexity of distributed minimum spanning tree algorithms. In Proceedings, 2nd Berkeley Conference on Distributed Data Management and Computer Networks, Berkeley, Calif., June 1977.
	9	YAO, A.C.C. An O(E log log V) algorithm for finding minimum spanning trees. Inf. Process. Lett. 4 (1975), 21-23.

CITED BY 124

	Mohan Sharma , Jianhua Chen , Sitharama Iyengar, Distributed algorithms for locating centers and medians in communication networks, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.808-817, March 1992, Kansas City, Missouri, United States
	Yehuda Afek , Baruch Awerbuch , Serge Plotkin , Michael Saks, Local management of a global resource in a communication network, Journal of the ACM (JACM), v.43 n.1, p.1-19, Jan. 1996
	Baruch Awerbuch , Alan Baratz , David Peleg, Cost-sensitive analysis of communication protocols, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.177-187, August 22-24, 1990, Quebec City, Quebec, Canada
	Baruch Awerbuch , Shay Kutten , David Peleg, Efficient deadlock-free routing, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.177-188, August 19-21, 1991, Montreal, Quebec, Canada
	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985
	Shay Kutten , David Peleg, Fast distributed construction of k-dominating sets and applications, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.238-251, August 20-23, 1995, Ottowa, Ontario, Canada
	E. Korach , S. Moran , S. Zaks, Tight lower and upper bounds for some distributed algorithms for a complete network of processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.199-207, August 27-29, 1984, Vancouver, British Columbia, Canada
	Yehuda Afek , Gad M. Landau , Baruch Schieber , Moti Yung, The power of multimedia: combining point-to point and multi-access networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.90-104, August 15-17, 1988, Toronto, Ontario, Canada
	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
	Harry Buhrman , Matthew Franklin , Juan A. Garay , Jaap-Henk Hoepman , John Tromp , Paul Vitányi, Mutual search, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.481-489, January 25-27, 1998, San Francisco, California, United States
	Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984
	E Korach , D Rotem , N Santoro, Distributed algorithms for finding centers and medians in networks, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.380-401, July 1984
	Amotz Bar-Noy , Joseph Naor , Moni Naor, One bit algorithms, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.66-76, August 15-17, 1988, Toronto, Ontario, Canada
	Jennifer L. Welch , Leslie Lamport , Nancy Lynch, A lattice-structured proof of a minimum spanning, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.28-43, August 15-17, 1988, Toronto, Ontario, Canada
	Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001
	Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995
	Ching Tsun Chou , Eli Gafni, Understanding and verifying distributed algorithms using stratified decomposition, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.44-65, August 15-17, 1988, Toronto, Ontario, Canada
	Baruch Awerbuch , Israel Cidon , Inder Gopal , Marc Kaplan , Shay Kutten, Distributed control for PARIS, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.145-159, August 22-24, 1990, Quebec City, Quebec, Canada
	Harry Buhrman , Matthew Franklin , Juan A. Garay , Jaap-Henk Hoepman , John Tromp , Paul Vitányi, Mutual search, Journal of the ACM (JACM), v.46 n.4, p.517-536, July 1999
	I A Cimet , P R Srikanta Kumar, A resilient distributed protocol for network synchronization, ACM SIGCOMM Computer Communication Review, v.16 n.3, p.358-367, Aug. 5, 1986
	Michalis Faloutsos , Mart Molle, Optimal distributed algorithm for minimum spanning trees revisited, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.231-237, August 20-23, 1995, Ottowa, Ontario, Canada
	Seapahn Meguerdichian , Sasa Slijepcevic , Vahag Karayan , Miodrag Potkonjak, Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA
	Yuanzhu Peter Chen , Arthur L. Liestman, Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland
	J. Nehmer , T. Becker, A fault tolerance approach for distributed ISDN control systems, Proceedings of the 4th workshop on ACM SIGOPS European workshop, p.1-4, September 03-05, 1990, Bologna, Italy
	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
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	Paola Flocchini , Bernard Mans , Nicola Santoro, Sense of direction in distributed computing, Theoretical Computer Science, v.291 n.1, p.29-53, 4 January 2003
	Fred Bauer , Anujan Varma, Distributed algorithms for multicast path setup in data networks, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.181-191, April 1996
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.265-274, May 01-04, 1999, Atlanta, Georgia, United States
	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States
	Wil Janssen , Job Zwiers, From sequential layers to distributed processes: deriving a distributed minimum weight spanning tree algorithm, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.215-227, August 10-12, 1992, Vancouver, British Columbia, Canada
	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988
	Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987
	Yehuda Afek , Eli Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.186-195, August 1985, Minaki, Ontario, Canada
	Baruch Awerbuch , Lenore J. Cowen , Mark A. Smith, Efficient asynchronous distributed symmetry breaking, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.214-223, May 23-25, 1994, Montreal, Quebec, Canada
	Yehuda Afek , Michael Saks, Detecting global termination conditions in the face of uncertainty, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.109-124, August 10-12, 1987, Vancouver, British Columbia, Canada
	Zvi Lotker , Boaz Patt-Shamir , David Peleg, Distributed MST for constant diameter graphs, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.63-71, August 2001, Newport, Rhode Island, United States
	Eli Gafni , Yehuda Afek, Election and traversal in unidirectional networks, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.190-198, August 27-29, 1984, Vancouver, British Columbia, Canada
	A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States
	Marc Bui , Franck Butelle , Christian Lavault, A distributed algorithm for constructing a minimum diameter spanning tree, Journal of Parallel and Distributed Computing, v.64 n.5, p.571-577, May 2004
	David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.77-85, August 10-12, 1987, Vancouver, British Columbia, Canada
	H. Baala , O. Flauzac , J. Gaber , M. Bui , T. El-Ghazawi, A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks, Journal of Parallel and Distributed Computing, v.63 n.1, p.97-104, January 2003
	Pierre Fraigniaud , Cyril Gavoille , Bernard Mans, Interval routing schemes allow broadcasting with linear message-complexity (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.11-20, July 16-19, 2000, Portland, Oregon, United States
	Shay Kutten , David Peleg , Uzi Vishkin, Deterministic resource discovery in distributed networks, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.77-83, July 2001, Crete Island, Greece
	E. Korach , S. Moran , S. Zaks, The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.277-286, August 1985, Minaki, Ontario, Canada
	Baruch Awerbuch, Communication-time trade-offs in network synchronization, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.272-276, August 1985, Minaki, Ontario, Canada
	Baruch Awerbuch , Oded Goldreich , Ronen Vainish , David Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM (JACM), v.37 n.2, p.238-256, April 1990
	E. Korach , S. Kutten , S. Moran, A modular technique for the design of efficient distributed leader finding algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.163-174, August 1985, Minaki, Ontario, Canada
	Leslie Lamport, win and sin: predicate transformers for concurrency, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.396-428, July 1990
	Nancy A. Lynch , Mark R. Tuttle, Hierarchical correctness proofs for distributed algorithms, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.137-151, August 10-12, 1987, Vancouver, British Columbia, Canada
	Mario Ζagalj , Jean-Pierre Hubaux , Christian Enz, Minimum-energy broadcast in all-wireless networks:: NP-completeness and distribution issues, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA
	Xiaohua Jia, A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks, IEEE/ACM Transactions on Networking (TON), v.6 n.6, p.828-837, Dec. 1998
	C. Cheng , I. Cimet , S. Kumar, A protocol to maintain a minimum spanning tree in a dynamic topology, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.330-337, August 1988
	Michael J. McGlynn , Steven A. Borbash, Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA
	Boris Koldehofe , Marina Papatriantafilou , Philippas Tsigas, Distributed algorithms visualisation for educational purposes, ACM SIGCSE Bulletin, v.31 n.3, p.103-106, Sept. 1999
	E. Korach , S. Kutten , S. Moran, A modular technique for the design of efficient distributed leader finding algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.84-101, Jan. 1990
	Yaacov Fernandess , Dahlia Malkhi, K-clustering in wireless ad hoc networks, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France
	Stefan Dobrev , Peter Ružička, On the communication complexity of strong time-optimal distributed algorithms, Nordic Journal of Computing, v.5 n.2, p.87-104, Summer 1998
	S. Venkatesan , Tony T-Y. Juang, Efficient algorithms for optimistic crash recovery, Distributed Computing, v.8 n.2, p.105-114, October 1994
	Nicola Santoro, Sense of direction, topological awareness and communication complexity, ACM SIGACT News, v.16 n.2, p.50-56, Summer 1984
	Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Liuba Shrira , Nissim Francez , Michael Rodeh, Distributed k-selection: From a sequential to a distributed algorithm, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.143-153, August 17-19, 1983, Montreal, Quebec, Canada
	Karni Gilon , David Peleg, Compact deterministic distributed dictionaries (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.81-94, August 19-21, 1991, Montreal, Quebec, Canada
	Dimiter R. Avresky, Embedding and Reconfiguration of Spanning Trees in Faulty Hypercubes, IEEE Transactions on Parallel and Distributed Systems, v.10 n.3, p.211-222, March 1999
	D. Chakraborty , G. Chakraborty , N. Shiratori, Multicast: concept, problems, routing protocols, algorithms and QoS extensions, Distributed multimedia databases: techniques & applications, Idea Group Publishing, Hershey, PA, 2002
	Art Kazmierczak , Sridhar Radhakrishnan, An Optimal Distributed Ear Decomposition Algorithm with Applications to Biconnectivity and Outerplanarity Testing, IEEE Transactions on Parallel and Distributed Systems, v.11 n.2, p.110-118, February 2000
	Seyed H. Hosseini , Nizar Jamal, Efficient Distributed Algorithms for Self Testing of Multiple Processor Systems, IEEE Transactions on Computers, v.41 n.11, p.1397-1409, November 1992
	Alon Itai , Shay Kutten , Yaron Wolfstahl , Shmuel Zaks, Optimal Distributed t-Resilient Election in Complete Networks, IEEE Transactions on Software Engineering, v.16 n.4, p.415-420, April 1990
	K. V. S. Ramarao, Distributed Algorithms for Network Recognition Problems, IEEE Transactions on Computers, v.38 n.9, p.1240-1248, September 1989
	Jean-François Macq , Michel X. Goemans, Trade-offs on the location of the core node in a network, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Hüseyin Özgür Tan , Ibrahim Körpeoǧlu, Power efficient data gathering and aggregation in wireless sensor networks, ACM SIGMOD Record, v.32 n.4, December 2003
	Gady Kozma , Zvi Lotker , Micha Sharir , Gideon Stupp, Geometrically aware communication in random wireless networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	J. Cao , Y. Liu , Li Xie , B. Mao , K. Zhang, The design and implementation of a runtime system for graph-oriented parallel and distributed programming, Journal of Systems and Software, v.72 n.3, p.389-399, August 2004
	Bernard Mans , Nicola Santoro, Optimal Elections in Faulty Loop Networks and Applications, IEEE Transactions on Computers, v.47 n.3, p.286-297, March 1998
	S. Venkatesan , Tony Tong-Ying Juang , Sridhar Alagar, Optimistic Crash Recovery without Changing Application Messages, IEEE Transactions on Parallel and Distributed Systems, v.8 n.3, p.263-271, March 1997
	Alberto Negro , Nicola Santoro , Jorge Urrutia, Efficient Distributed Selection with Bounded Messages, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.397-401, April 1997
	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
	A. Bagchi , S. L. Hakimi, Information Dissemination in Distributed Systems with Faulty Units, IEEE Transactions on Computers, v.43 n.6, p.698-710, June 1994
	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
	Michael Elkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Gurdip Singh , Arthur J. Bernstein, A highly asynchronous minimum spanning tree protocol, Distributed Computing, v.8 n.3, p.151-161, March 1995
	MohammadTaghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu , Yitong Yin, Fast construction of overlay networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Zvi Lotker , Elan Pavlov , Boaz Patt-Shamir , David Peleg, MST construction in O(log log n) communication rounds, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Carlos A. S. Oliveira , Panos M. Pardalos, A survey of combinatorial optimization problems in multicast routing, Computers and Operations Research, v.32 n.8, p.1953-1981, August 2005
	Israel Cidon, An Efficient Distributed Knot Detection Algorithm, IEEE Transactions on Software Engineering, v.15 n.5, p.644-649, May 1989
	Giovanni Di Crescenzo , Maria Striki , John S. Baras, Modeling key agreement in multi-hop ad hoc networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
	Wei Shi , Pradip K. Srimani, Leader election in hierarchical star network, Journal of Parallel and Distributed Computing, v.65 n.11, p.1435-1442, November 2005
	Amos Korman , Shay Kutten, Distributed verification of minimum spanning trees, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Ioannis Papadimitriou , Leonidas Georgiadis, Minimum-energy broadcasting in multi-hop wireless networks using a single broadcast tree, Mobile Networks and Applications, v.11 n.3, p.361-375, June 2006
	Gruia Calinescu , Peng-jun Wan, Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks, Mobile Networks and Applications, v.11 n.2, p.121-128, April 2006
	M. S. Kordafshari , M. Gholipour , M. Jahanshahi , A. T. Haghighat, Two novel algorithms for electing coordinator in distributed systems basedon bully algorithm, Proceedings of the 4th WSEAS International Conference on Software Engineering, Parallel & Distributed Systems, p.1-6, February 13-15, 2005, Salzburg, Austria
	Mohammad Taghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, IEEE/ACM Transactions on Networking (TON), v.15 n.6, p.1345-1358, December 2007
	Intae Kang , Radha Poovendran, Maximizing network lifetime of broadcasting over wireless stationary ad hoc networks, Mobile Networks and Applications, v.10 n.6, p.879-896, December 2005
	Xiang-Yang Li, Localized construction of low weighted structure and its applications in wireless ad hoc networks, Wireless Networks, v.11 n.6, p.697-708, November 2005
	Mario Čagalj , Jean-Pierre Hubaux , Christian C. Enz, Energy-efficient broadcasting in all-wireless networks, Wireless Networks, v.11 n.1-2, p.177-188, January 2005
	Alpár Jüttner , Ádám Magi, Tree based broadcast in ad hoc networks, Mobile Networks and Applications, v.10 n.5, p.753-762, October 2005
	Azzedine Boukerche , Kaouther Abrougui, An efficient leader election protocol for mobile networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
	Bo Han , Weijia Jia, Clustering wireless ad hoc networks with weakly connected dominating set, Journal of Parallel and Distributed Computing, v.67 n.6, p.727-737, June, 2007
	Luca Gatani , Giuseppe Lo Re , Salvatore Gaglio, An efficient distributed algorithm for generating and updating multicast trees, Parallel Computing, v.32 n.11-12, p.777-793, December, 2006
	Gayathri Venkataraman , Sabu Emmanuel , Srikanthan Thambipillai, Size-restricted cluster formation and cluster maintenance technique for mobile ad hoc networks, International Journal of Network Management, v.17 n.2, p.171-194, March 2007
	Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Journal of Computer and System Sciences, v.72 n.8, p.1282-1308, December, 2006
	Song Guo , Oliver W. W. Yang, Energy-aware multicasting in wireless ad hoc networks: A survey and discussion, Computer Communications, v.30 n.9, p.2129-2148, June, 2007
	Christian Lavault , Mario Valencia-Pabon, A distributed approximation algorithm for the minimum degree minimum weight spanning trees, Journal of Parallel and Distributed Computing, v.68 n.2, p.200-208, February, 2008
	Chee-Wei Ang , Chen-Khong Tham, iMST: A bandwidth-guaranteed topology control algorithm for TDMA-based ad hoc networks with sectorized antennas, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.9, p.1675-1692, June, 2008
	Yongwook Choi , Maleq Khan , V.S. Anil Kumar , Gopal Pandurangan, Energy-optimal distributed algorithms for minimum spanning trees, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Pierre Fraigniaud , Amos Korman , Emmanuelle Lebhar, Local MST computation with short advice, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Vinod Namboodiri , Lixin Gao , Ramakrishna Janaswamy, Power-efficient topology control for static wireless networks with switched beam directional antennas, Ad Hoc Networks, v.6 n.2, p.287-306, April, 2008
	Qing Dai , Jie Wu, Computation of Minimal Uniform Transmission Range in Ad Hoc Wireless Networks, Cluster Computing, v.8 n.2-3, p.127-133, July 2005
	Tomoko Suzuki , Taisuke Izumi , Fukuhito Ooshita , Hirotsugu Kakugawa , Toshimitsu Masuzawa, Move-optimal gossiping among mobile agents, Theoretical Computer Science, v.393 n.1-3, p.90-101, March, 2008
	J. Nehmer , T. Becker, A fault tolerance approach for distributed ISDN control systems, ACM SIGOPS Operating Systems Review, v.25 n.2, p.126-129, April 1991
	Raghupathy Sivakumar , Bevan Das , Vaduvur Bharghavan, Spine routing in ad hoc networks, Cluster Computing, v.1 n.2, p.237-248, 1998
	Changhan Kim , Younghoon Kim , Jae-Heon Yang , Ikjun Yeom, Analysis of bandwidth efficiency in overlay multicasting, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.2, p.384-398, February, 2008
	Maleq Khan , Gopal Pandurangan , V. S. Anil Kumar, A simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms, Theoretical Computer Science, v.385 n.1-3, p.101-114, October, 2007
	Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings, Journal of the ACM (JACM), v.55 n.1, p.1-28, February 2008
	Shantanu Das , Paola Flocchini , Shay Kutten , Amiya Nayak , Nicola Santoro, Map construction of unknown graphs by multiple agents, Theoretical Computer Science, v.385 n.1-3, p.34-48, October, 2007
	Shoudong Zou , Ioanis Nikolaidis , Janelle Harms, Efficient aggregation using first hop selection in WSNs, International Journal of Sensor Networks, v.4 n.1/2, p.55-67, July 2008
	Tiziana Calamoneri , Andrea E.F. Clementi , Angelo Monti , Gianluca Rossi , Riccardo Silvestri, Minimum-energy broadcast in random-grid ad-hoc networks: approximation and distributed algorithms, Proceedings of the 11th international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 27-31, 2008, Vancouver, British Columbia, Canada
	Maleq Khan , Fabian Kuhn , Dahlia Malkhi , Gopal Pandurangan , Kunal Talwar, Efficient distributed approximation algorithms via probabilistic tree embeddings, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Baruch Awerbuch , Israel Cidon , Shay Kutten, Optimal maintenance of a spanning tree, Journal of the ACM (JACM), v.55 n.4, p.1-45, September 2008
	Yangfan Zhou , Michael R. Lyu , Jiangchuan Liu, On sensor network reconfiguration for downtime-free system migrations, Proceedings of the 5th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness, July 28-31, 2008, Hong Kong
	Katsutoshi Hirayama , Toshihiro Matsui , Makoto Yokoo, Adaptive price update in distributed Lagrangian relaxation protocol, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	Theodore Elhourani , Nathan Denny , Michael Marefat, A distributed constraint optimization solution to the P2P video streaming problem, Proceedings of the 22nd national conference on Artificial intelligence, p.1347-1352, July 22-26, 2007, Vancouver, British Columbia, Canada
	Andrew Adamatzky, From reaction-diffusion to Physarum computing, Natural Computing: an international journal, v.8 n.3, p.431-447, September 2009