Article

Free access

Fast randomized algorithms for distributed edge coloring

Authors:

Alessandro Panconesi,

Aravind SrinivasanAuthors Info & Claims

PODC '92: Proceedings of the eleventh annual ACM symposium on Principles of distributed computing

Pages 251 - 262

https://doi.org/10.1145/135419.135465

Published: 01 October 1992 Publication History

PDF eReader

References

[1]

N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7:567-5837 1986.

Digital Library

Google Scholar

[2]

B. Awerbuch. Complexity of network synchronization. J. Assoc. Comput. Mach., 32:804-823, 1985.

Digital Library

Google Scholar

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

Digital Library

Google Scholar

[4]

B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM J. on Discrete Mathematics, 5(2), 1992.

Digital Library

Google Scholar

[5]

B. Berger and L. Cowen. Fast deterministic constructions of low-diameter network decompositions. MiT-LCS Technical Memo ~460, April 1991.

Google Scholar

[6]

B. Berger and J. Rompel. Simulating (log~ n)-wise independence in NC. J. Assoc. Comput. Mach., 38(4):1026-1046, 1991.

Digital Library

Google Scholar

[7]

B. Bollob~. Graph Theory. Springer Verlag, New York, 1979.

Google Scholar

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

Crossref

Google Scholar

[9]

W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, pages 13-30, 1963.

Crossref

Google Scholar

[10]

It. J. Karloff and D. B. Shmoys. Efficient parallel algorithms for edge coloring problems. Journal of Algorithms, 8:39-52, 1987.

Digital Library

Google Scholar

[11]

N. Linial and M. Saks. Decomposing graphs into regions of small diameter. In Proceedings of the A CM/SIAM Symposium on Discrete Algorithms, pages 320-330, 1991.

Digital Library

Google Scholar

[12]

M. Luby. A fast parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036-1053, 1986.

Digital Library

Google Scholar

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

Google Scholar

[14]

R. Motwani, J. Naor, and M. Naor. The probabilistic method yields deterministic parallel algorithms. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 8-13, 1989.

Digital Library

Google Scholar

[15]

A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In A CM Symposium on Theory of Computing, pages 581-592, 1992.

Digital Library

Google Scholar

[16]

P. Raghavan. Randomized Rounding and Discrete Ham-Sandwich Theorems: Provably Good Algorithms for Routing and Packing Problems. PhD thesis, University of California at Berkeley, July 1986. Also available as Computer Science Department Report UCB/CSD 87/312.

Digital Library

Google Scholar

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

Google Scholar

[18]

R. Raman. The power of Collision: Randomized parallel algorithms for chaining and integer sorting. In Proceedings, l Oth Annual FST & TCS Conference, Lecture Notes in Computer Science ~P 472, pages 161-175. Springer-Verlag, Berlin, December 1990. Also available as University of Rochester CS Dept. TR 336, March 1990 (Revised January 1991).

Crossref

Google Scholar

Cited By

View all

Alvisi LDolev SEllen FKeidar IKuhn FSuomela JRobinson PEllen F(2019)2019 Edsger W. Dijkstra Prize in Distributed ComputingProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3341564(1-1)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3341564
Ghaffari MKuhn FMaus YUitto JDiakonikolas IKempe DHenzinger M(2018)Deterministic distributed edge-coloring with fewer colorsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188906(418-430)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188906
Kothapalli KScheideler COnus MSchindelhauer C(2006)Distributed coloring in Õ (√log n) Bit RoundsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1898978(44-44)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1898978
Show More Cited By

Index Terms

Fast randomized algorithms for distributed edge coloring
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation

Recommendations

Distributed Edge Coloring in Time Polylogarithmic in Δ
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a (2Δ - 1)-edge coloring can be computed in time poly ...
About randomised distributed graph colouring and graph partition algorithms

We present and analyse a very simple randomised distributed vertex colouring algorithm for arbitrary graphs of size n that halts in time O(logn) with probability 1-o(n^-^1). Each message containing 1 bit, its bit complexity per channel is O(logn). From ...
Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems

LetG(V,E) be a simple undirected graph with a maximum vertex degree (G) (or for short), |V| =nand |E| =m. An edge-coloring ofGis an assignment to each edge inGa color such that all edges sharing a common vertex have different colors. The minimum number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '92: Proceedings of the eleventh annual ACM symposium on Principles of distributed computing

October 1992

304 pages

ISBN:0897914953

DOI:10.1145/135419

Chairman:
Norman C. Hutchinson
Univ. of British Columbia, Vancouver, B. C., Canada

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC92

Sponsor:

PODC92: 11th Annual ACM Symposium in Principles of Distributed Computing

August 10 - 12, 1992

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
647
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)8

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Alvisi LDolev SEllen FKeidar IKuhn FSuomela JRobinson PEllen F(2019)2019 Edsger W. Dijkstra Prize in Distributed ComputingProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3341564(1-1)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3341564
Ghaffari MKuhn FMaus YUitto JDiakonikolas IKempe DHenzinger M(2018)Deterministic distributed edge-coloring with fewer colorsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188906(418-430)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188906
Kothapalli KScheideler COnus MSchindelhauer C(2006)Distributed coloring in Õ (√log n) Bit RoundsProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1898978(44-44)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1898978
Sakurai YOoshita FMasuzawa T(2006)A Self-Stabilizing Link-Coloring Protocol in Tree Networks with Permanent Byzantine FaultsJournal of Aerospace Computing, Information, and Communication10.2514/1.198223:8(420-436)Online publication date: Aug-2006
https://doi.org/10.2514/1.19822
Kothapalli KScheideler COnus MSchindelhauer C(2006)Distributed coloring in O/spl tilde/(/spl radic/(log n)) bit roundsProceedings 20th IEEE International Parallel & Distributed Processing Symposium10.1109/IPDPS.2006.1639281(10 pp.)Online publication date: 2006
https://doi.org/10.1109/IPDPS.2006.1639281
Patt-Shamir BShafrir A(2006)Approximate top-k queries in sensor networksProceedings of the 13th international conference on Structural Information and Communication Complexity10.1007/11780823_25(319-333)Online publication date: 2-Jul-2006
https://dl.acm.org/doi/10.1007/11780823_25
Wu JLin YLiu P(2005)Efficient Distributed Algorithms for Parallel I/O SchedulingProceedings of the 11th International Conference on Parallel and Distributed Systems - Volume 0110.1109/ICPADS.2005.140(460-466)Online publication date: 20-Jul-2005
https://dl.acm.org/doi/10.1109/ICPADS.2005.140
Dubhashi DPanconesi A(2005)Near-optimal distributed edge coloringAlgorithms — ESA '9510.1007/3-540-60313-1_162(448-459)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-60313-1_162
Chaudhuri SDubhashi D(2005)(Probabilistic) recurrence relations revisitedLATIN '95: Theoretical Informatics10.1007/3-540-59175-3_90(207-219)Online publication date: 6-Jun-2005
https://doi.org/10.1007/3-540-59175-3_90
Leonardi SMarchetti-Spaccamela AMeyer auf der Heide FGibbons PAdler M(2004)Scheduling against an adversarial networkProceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1007912.1007936(151-159)Online publication date: 27-Jun-2004
https://dl.acm.org/doi/10.1145/1007912.1007936
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Distributed Edge Coloring in Time Polylogarithmic in Δ

About randomised distributed graph colouring and graph partition algorithms

Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems