Fast distributed construction of k-dominating sets and applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast distributed construction of k-dominating sets and applications

Full text

Pdf (1.30 MB)

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: 238 - 251

Year of Publication: 1995

ISBN:0-89791-710-3

Authors

Shay Kutten	I.B.M. T.J. Watson Research Center, P.O. Box 704, Yorktown, Heights, New York
David Peleg	Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, 76100 Israel

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): 4, Downloads (12 Months): 39, Citation Count: 7

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.224990 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.

	AG	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 [doi>10.1145/323596.323613]
	AK	Sudhanshu Aggarwal , Shay Kutten, Time Optimal Self-Stabilizing Spanning Tree Algorithms, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.400-410, December 15-17, 1993
	A1	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	A2	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]
	AKMPV	Baruch Awerbuch , Shay Kutten , Yishay Mansour , Boaz Patt-Shamir , George Varghese, Time optimal self-stabilizing synchronization, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.652-661, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167256]
	AGLP	B. Awerbuch, A. Goldberg, M. Luby and S. Plotkin, Network decomposition and locality in distributed computation, Proc. 30th Symp. on Foundations o~ Computer Science, pp. 364-375, October 1989.
	BKP	Judit Bar-Ilan , Guy Kortsarz , David Peleg, How to allocate network centers, Journal of Algorithms, v.15 n.3, p.385-415, Nov. 1993 [doi>10.1006/jagm.1993.1047]
	CT	F. Chin and H. F. Ting, An Almost Linear Time and O(nlog(n)+ e) Messages Distributed Algorithm for Minimum-Weight Spanning Trees, 26th Symp. on Foundations o~ Computer Science, Oct. 1985, pages 257-266.
	CGS	E J Cockayne , B Gamble , B Shepherd, An upper bound for the k-domination number of a graph, Journal of Graph Theory, v.9 n.4, p.533-534, Dec. 1985 [doi>10.1002/jgt.3190090414]
	CN	G.J. Chang and G.L. Nemhauser, The k- Domination and k-Stability Problems on Sun- Free Chordal Graphs, SIAM J. Alg. & Disc. Moth. Vol. 5, (1984), 332-345.
	G	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]
	GHS	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]
	GKP	J. Garay, S. Kutten and D. Peleg, A Sub-Linear Time Distributed Algorithm for Minimum- Weight Spanning Trees, 34th IEEE Symp. on Foundations of Computer Science, pages 659- 668, November 1993.
	GPS	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 [doi>10.1145/28395.28429]
	JM	Donald B. Johnson , Panagiotis Metaxas, Connected components in O(lg3/2\|V\|) parallel time for the CREW PRAM (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.688-697, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185437]
	L	N. Linial, Distributive graph algorithms - global solutions from local data, Proc. 28th IEEE Symp. on Foundations of Computer Science, October 1987, pp. 331-335.
	P	David Peleg, Time-optimal leader election in general networks, Journal of Parallel and Distributed Computing, v.8 n.1, p.96-99, Jan. 1990 [doi>10.1016/0743-7315(90)90074-Y]
	P2	David Peleg, Distributed data structures: a complexity-oriented view, Proceedings of the 4th international workshop on Distributed algorithms, p.71-89, June 1991, Bari, Italy
	PS	Alessandro Panconesi , Aravind Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.581-592, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129769]
	PU	David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
	T	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

CITED BY 7

	Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, On the distributed complexity of computing maximal matchings, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.219-225, January 25-27, 1998, San Francisco, California, United States
	Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, A faster distributed algorithm for computing maximal matchings deterministically, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.219-228, May 04-06, 1999, Atlanta, Georgia, United States
	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
	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. Czygrinow , M. Hańćkowiak, Distributed algorithms for weighted problems in sparse graphs, Journal of Discrete Algorithms, v.4 n.4, p.588-607, December, 2006
	Giovanni Di Crescenzo , Mariusz Fecko , Renwei Ge , Gonzalo R. Arce, Securing Weakly-Dominating Virtual Backbones in Mobile Ad Hoc Networks, Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, p.576-580, June 26-29, 2006
	Raghupathy Sivakumar , Bevan Das , Vaduvur Bharghavan, Spine routing in ad hoc networks, Cluster Computing, v.1 n.2, p.237-248, 1998