article

An experimental study of a simple, distributed edge-coloring algorithm

Authors:

Madhav V. Marathe,

Alessandro Panconesi,

Larry D. Risinger, jrAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 9

Pages 1.3 - es

https://doi.org/10.1145/1005813.1041515

Published: 31 December 2004 Publication History

Get Access

Abstract

We conduct an experimental analysis of a distributed randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple yet, according to the probabilistic analysis, it computes nearly optimal colorings very quickly [Grable and Panconesi 1997]. We test the algorithm on a number of random as well as nonrandom graph families.The test cases were chosen based on two objectives: (i) to provide insights into the worst-case behavior (in terms of time and quality) of the algorithm and (ii) to test the performance of the algorithm with instances that are likely to arise in practice. Our main results include the following:(1) The empirical results obtained compare very well with the recent empirical results reported by other researchers [Durand et al. 1994, 1998; Jain and Werth 1995].(2) The empirical results confirm the bounds on the running time and the solution quality as claimed in the theoretical paper. Our results show that for certain classes of graphs the algorithm is likely to perform much better than the analysis suggests.(3) The results demonstrate that the algorithm might be well suited (from a theoretical as well as practical standpoint) for edge coloring graphs quickly and efficiently in a distributed setting.Based on our empirical study, we propose a simple modification of the original algorithm with substantially improved performance in practice.

References

[1]

Dubhashi, D., Grable, D., and Panconesi, A. 1998. Nearly-optimal, distributed edge-coloring via the nibble method. TCS 203, 4, 225--251. A special issue for the best papers of the 3rd European Symposium on Algorithms (ESA 95).

Crossref

Google Scholar

[2]

Durand, D., Jain, R., and Tseytlin, D. 1994. Distributed Scheduling Algorithms to Improve the Performance of Parallel Data Transfers. In ACM SIGARCH Computer Architecture News. ACM Press, 35--40. Special issue on Input/Output in Parallel Computer Systems.

Crossref

Google Scholar

[3]

Durand, D., Jain, R., and Tseytlin, D. 1998. Applying randomized edge-coloring algorithms to distributed communications: An experimental study. TCS 203, 4, 225--251. A special issue for the best papers of the 3rd European Symposium on Algorithms (ESA 95).

Google Scholar

[4]

Ferrell, R., Kothe, D., and Turner, J. 1997. PGSLib: A library for portable, parallel, unstructured mesh simulations. In Presented at the 8th SIAM Conference on Parallel Processing for Scientific Computing.

Google Scholar

[5]

Finocchi, I., Panconesi, A., and Silvestri, R. 2002. An experimental study of simple, distributed vertex colouring algorithms. In Proceedings of the Thirteenth ACM-SIAM Symposium on Discrete Algorithms (SODA 02). ACM Press, 245--269. To appear in Algorithmica.

Crossref

Google Scholar

[6]

Gabow, H. and Kariv, O. 1982. Algorithms for edge-coloring bipartite graphs and multigraphs. SIAM J. Comput. 1, 11, 117--129.

Google Scholar

[7]

Grable, D. and Panconesi, A. 1997. Nearly optimal distributed edge-coloring in o(log log n) rounds. RSA 10, 3 (May), 385--405. Also In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997, pp. 278--285.

Crossref

Google Scholar

[8]

Hochbaum, D., Eds. 1997. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, MA.

Crossref

Google Scholar

[9]

Hoyler, I. 1980. The NP-completeness of edge colorings. SIAM J. Comput. 10, 718--720.

Google Scholar

[10]

Jain, R., Somalwar, K., Werth, J., and Browne, J. 1992a. Scheduling parallel I/O operations in multiple bus systems. J. Parallel Distrib. Comput. 16, 4, 352--362.

Google Scholar

[11]

Jain, R., Werth, J., Browne, J., and Sasaki, G. 1992b. A graph-theoretic model for the scheduling problem and its application to simultaneous resource scheduling. In Computer Science and Operations Research: New Developments in Their Interfaces. O. Balci, R. Shander, and S. Zerrick, Eds. Penguin Press.

Google Scholar

[12]

Jain, R. and Werth, J. 1995. Analysis of approximate algorithms for edge-coloring bipartite graphs. IPL 54, 3, 163--168.

Crossref

Google Scholar

[13]

Kothe, D., Ferrell, R., Turner, J., and Mosso, S. 1997. A high resolution finite volume method for efficient parallel simulation of casting processes on unstructured meshes. In Presented at the 8th SIAM Conference on Parallel Processing for Scientific Comput. LANL Report LA-UR-97-30, 14--17.

Google Scholar

[14]

Panconesi, A. and Srinivasan, A. 1992. Fast randomized algorithms for distributed edge coloring. SIAM J. Comput. 26, 2, 350--368. Also in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 1992.

Crossref

Google Scholar

Cited By

View all

Maan VPurohit G(2013)A novel frequency allocation mechanism with separation in mobile cellular network based on distributed setting2013 International Conference on Advanced Electronic Systems (ICAES)10.1109/ICAES.2013.6659419(319-321)Online publication date: Sep-2013
https://doi.org/10.1109/ICAES.2013.6659419
Venkataraman HPurohit APareek RMuntean G(2012)Radio Resource Allocation for Cognitive Radio Based Ad hoc Wireless NetworksCognitive Radio and its Application for Next Generation Cellular and Wireless Networks10.1007/978-94-007-1827-2_11(287-305)Online publication date: 28-Apr-2012
https://doi.org/10.1007/978-94-007-1827-2_11
Choudhary SPurohit GMishra B(2010)Randomized distributed algorithm for vertex coloringProceedings of the International Conference and Workshop on Emerging Trends in Technology10.1145/1741906.1742013(477-480)Online publication date: 26-Feb-2010
https://dl.acm.org/doi/10.1145/1741906.1742013
Show More Cited By

Index Terms

An experimental study of a simple, distributed edge-coloring algorithm

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 ...
An experimental study of a simple, distributed edge coloring algorithm
SPAA '00: Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures
We conduct an experimental analysis of a distributed, randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple, yet, according to the probabilistic analysis, it computes nearly optimal colorings very quickly [12]...
Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
Special Issue on Soda'18 and Regular Papers

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 9, Issue

2004

189 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/1005813

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 December 2004

Published in JEA Volume 9

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
1,289
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Maan VPurohit G(2013)A novel frequency allocation mechanism with separation in mobile cellular network based on distributed setting2013 International Conference on Advanced Electronic Systems (ICAES)10.1109/ICAES.2013.6659419(319-321)Online publication date: Sep-2013
https://doi.org/10.1109/ICAES.2013.6659419
Venkataraman HPurohit APareek RMuntean G(2012)Radio Resource Allocation for Cognitive Radio Based Ad hoc Wireless NetworksCognitive Radio and its Application for Next Generation Cellular and Wireless Networks10.1007/978-94-007-1827-2_11(287-305)Online publication date: 28-Apr-2012
https://doi.org/10.1007/978-94-007-1827-2_11
Choudhary SPurohit GMishra B(2010)Randomized distributed algorithm for vertex coloringProceedings of the International Conference and Workshop on Emerging Trends in Technology10.1145/1741906.1742013(477-480)Online publication date: 26-Feb-2010
https://dl.acm.org/doi/10.1145/1741906.1742013
Choudhary SPurohit G(2010)Distributed algorithm for optimized vertex coloring2010 International Conference on Methods and Models in Computer Science (ICM2CS-2010)10.1109/ICM2CS.2010.5706720(65-69)Online publication date: Dec-2010
https://doi.org/10.1109/ICM2CS.2010.5706720
Ismail MCoon JAhmed IArmour SKocak T(2009)High throughput layered decoding of LDPC codes2009 IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications10.1109/PIMRC.2009.5449721(1727-1731)Online publication date: Sep-2009
https://doi.org/10.1109/PIMRC.2009.5449721
Xuedan Zhang Jun Hong Lin Zhang Xiuming Shan Li V(2007)CC-TDMAProceedings of the 2007 IEEE Wireless Communications and Networking Conference10.1109/WCNC.2007.30(133-137)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.1109/WCNC.2007.30

View Options

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 Δ

An experimental study of a simple, distributed edge coloring algorithm

Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma