Improved distributed algorithms for coloring and network decomposition problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved distributed algorithms for coloring and network decomposition problems

Full text

Pdf (1.04 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 581 - 592

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Alessandro Panconesi	Department of Computer Science, Cornell University, Ithaca, NY
Aravind Srinivasan	Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 65, Citation Count: 15

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/129712.129769 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	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	2	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]
	3	B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proceedings o/ the IEEE Symposium on Foundations of Computer Science, pages 364-369, 1989.
	4	B. Awerbuch and D. Peleg. Sparse partitions. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 503-513, 1990.
	5	Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
	6	B. Berger and L. Cowen. Fast deterministic constructions of low-diameter network decompositions. MIT-LCS Technical Memo #460, April 1991.
	7	B. Bollob~s. Graph Theory. Springer Verlag, New York, 1979.
	8	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	9	Andrew V. Goldberg , Serge A. Plotkin , Gregory E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM Journal on Discrete Mathematics, v.1 n.4, p.434-446, Nov. 1988 [doi>10.1137/0401044]
	10	Péter Hajnal , Endre Szemerédi, Brooks coloring in parallel, SIAM Journal on Discrete Mathematics, v.3 n.1, p.74-80, Feb. 1990 [doi>10.1137/0403008]
	11	Mauricio Karchmer, A fast parallel algorithm to color graph with &Dgr; colors, Journal of Algorithms, v.9 n.1, p.83-91, March 1988 [doi>10.1016/0196-6774(88)90006-5]
	12	H. J. Karloff, An NC algorithm for Brooks' theorem, Theoretical Computer Science, v.68 n.1, p.89-103, Oct. 16, 1989 [doi>10.1016/0304-3975(89)90121-7]
	13	G. F. Lev, N. Pippenger, and L. G. Valiant. A fast parallel algorithm for routing in permutation networks. IEEE Transactions on Computers, 30:93- 100, 1981.
	14	N. Linial. Distributive algorithms-global solutions from local data. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 331-335, 1987.
	15	Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
	16	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	17	M. Luby. Removing randomness in parallel computation without a processor penalty. In Procecd#r#g# of the IEEE Symposium on Foundations of Computer Science, pages 162-173, 1988.

CITED BY 15

	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
	Moni Naor , Larry Stockmeyer, What can be computed locally?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.184-193, May 16-18, 1993, San Diego, California, United States
	Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
	Gianluca De Marco , Andrzej Pelc, Fast distributed graph coloring with O(&Dgr;) colors, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.630-635, January 07-09, 2001, Washington, D.C., United States
	Alessandro Panconesi , Aravind Srinivasan, Fast randomized algorithms for distributed edge coloring, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.251-262, August 10-12, 1992, Vancouver, British Columbia, Canada
	Lucia Draque Penso , Valmir C. Barbosa, A distributed algorithm to find k-dominating sets, Discrete Applied Mathematics, v.141 n.1-3, p.243-253, 30 May 2004
	Suresh Chari , Pankaj Rohatgi , Aravind Srinivasan, Improved algorithms via approximations of probability distributions (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.584-592, May 23-25, 1994, Montreal, Quebec, Canada
	Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Fast network decomposition, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.169-177, August 10-12, 1992, Vancouver, British Columbia, Canada
	Magnús Halldórsson , Jaikumar Radhakrishnan, Greed is good: approximating independent sets in sparse and bounded-degree graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.439-448, May 23-25, 1994, Montreal, Quebec, Canada
	Weizhao Wang , Xiang-Yang Li , Ophir Frieder , Yu Wang , Wen-Zhan Song, Efficient interference-aware TDMA link scheduling for static wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Shashidhar Gandham , Milind Dawande , Ravi Prakash, Link scheduling in wireless sensor networks: Distributed edge-coloring revisited, Journal of Parallel and Distributed Computing, v.68 n.8, p.1122-1134, August, 2008
	Beat Gfeller , Elias Vicari, A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Johannes Schneider , Roger Wattenhofer, A log-star distributed maximal independent set algorithm for growth-bounded graphs, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Gladstone M. Arantes, Jr. , Felipe M. G. França , Carlos A. Martinhon, Randomized generation of acyclic orientations upon anonymous distributed systems, Journal of Parallel and Distributed Computing, v.69 n.3, p.239-246, March, 2009