Fast randomized algorithms for distributed edge coloring

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast randomized algorithms for distributed edge coloring

Full text

Pdf (946 KB)

Source

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

Vancouver, British Columbia, Canada

Pages: 251 - 262

Year of Publication: 1992

ISBN:0-89791-495-3

Authors

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

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): 5, Downloads (12 Months): 28, Citation Count: 9

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/135419.135465 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 of the I~EE Symposium on Foundahons of Computer Science, pages 364-369, 1989.
	4	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]
	5	B. Berger and L. Cowen. Fast deterministic constructions of low-diameter network decompositions. MiT-LCS Technical Memo ~460, April 1991.
	6	Bonnie Berger, Simulating (logcn)-wise independence in NC, Journal of the ACM (JACM), v.38 n.4, p.1026-1046, Oct. 1991 [doi>10.1145/115234.115347]
	7	B. Bollob~. Graph Theory. Springer Verlag, New York, 1979.
	8	H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493- 509, 1952.
	9	W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, pages 13-30, 1963.
	10	Howard J. Karloff , David B. Shmoys, Efficient parallel algorithms for edge coloring problems, Journal of Algorithms, v.8 n.1, p.39-52, March 1987 [doi>10.1016/0196-6774(87)90026-5]
	11	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
	12	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]
	13	M. Luby. Removing randomness in parallel computation without a processor penalty. In Proceedzngs of the {EEE Symposium on Foundations of Computer Science, pages 162-173, 1988.
	14	Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
	15	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]
	16	Prabhakar Raghavan, Randomized rounding and discrete ham-sandwich theorems: provably good algorithms for routing and packing problems (integer programming), 1986
	17	P. Raghavan. Lecture notes on randomized algorithms. Technical Report RC 15340 (~68237), IBM T.J.Watson Research Center, January 1990. Also available as CS661 Lecture Notes, Technical report YALE/DCS/RR-757, Department of Computer Science, Yale University, January 1990.
	18	Rajeev Raman, The power of Collision: randomized parallel algorithms for chaining and integer sorting, Proceedings of the tenth conference on Foundations of software technology and theoretical computer science, p.161-175, November 1990, Bangalore, India

CITED BY 9

	Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.331-340, January 25-27, 1993, Austin, Texas, United States
	Dannie Durand , Ravi Jain , David Tseytlin, Applying randomized edge coloring algorithms to distributed communication: an experimental study, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.264-274, June 24-26, 1995, Santa Barbara, California, United States
	David A. Grable , Alessandro Panconesi, Nearly optimal distributed edge colouring in O(log log n) rounds, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.278-285, January 05-07, 1997, New Orleans, Louisiana, United States
	Madhav V. Marathe , Alessandro Panconesi , Larry D. Risinger, An experimental study of a simple, distributed edge coloring algorithm, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.166-175, July 09-13, 2000, Bar Harbor, Maine, United States
	Stefano Leonardi , Alberto Marchetti-Spaccamela , Friedhelm Meyer auf der Heide, Scheduling against an adversarial network, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Dannie Durand , Ravi Jain , David Tseytlin, Parallel I/O scheduling using randomized, distributed edge coloring algorithms, Journal of Parallel and Distributed Computing, v.63 n.6, p.611-618, June 2003
	Anshul Gupta , Pankaj Rohatgi , Ramesh Agarwal, Fast practical algorithms for the Boolean-product-witness-matrix problem, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.146-152, July 2000, St. Andrews, Scotland
	Madhav V. Marathe , Alessandro Panconesi , Larry D. Risinger, jr, An experimental study of a simple, distributed edge-coloring algorithm, Journal of Experimental Algorithmics (JEA), v.9 n.es, 2004
	Dannie Durand , Ravi Jain , David Tseytlin, Distributed scheduling algorithms to improve the performance of parallel data transfers, ACM SIGARCH Computer Architecture News, v.22 n.4, p.35-40, Sept. 1994