Randomized distributed algorithm for vertex coloring
Abstract
Many computational tasks require the cooperation of many processors in the network, but prohibit certain processors pair (or large group) from operating simultaneously. This symmetry breaking technique play a major role in distributed network algorithm. Two symmetry breaking task of "localized" nature are coloring (Vertex Coloring) and Maximal Independence Set (MIS). In this paper, we present an experimental analysis of simple and elegant randomized distributed algorithm for vertex coloring problem
References
[1]
Alon N., Babai L., and Itai A. 1986 "A fast and simple randomized parallel algorithm for the maximal independent set problem". Journal of Algorithms, 7(4):567--583
[2]
Barenboim L. and Elkin M. 2009. "Distributed (Δ+1)- coloring in linear (in Δ) time", Annual ACM Symposium on Theory of Computing, Proceedings of the 41st annual ACM symposium on Theory of computing, 111--120
[3]
Cole R. and Vishkin U., 1986, "Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms", in Proc. 18th Symposium on Theory of Computing,. 206--219.
[4]
Elkin M. 2004. "Distributed approximation: A survey". ACM SIGACT News, 35(4):40--57
[5]
Finocchi, I., Panconesi, A., and Silvestri, R. 2002.: "Experimental analysis of simple, distributed vertex colouring algorithms". In Proc. of the ACM Symposium on Discrete Algorithms (SODA).
[6]
Hermann T. and Tixeuil S. 2004: "A distributed TDMA slot assignment algorithm for wireless sensor networks". In Proc. of 1st Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), volume 3121 of Lecture Notes in Computer Science, pages 45--58
[7]
Jia L., Rajaraman R., and Suel R. 2002: "An efficient distributed algorithm for constructing small dominating sets". Distributed Computing, 15(4):193--205.
[8]
Karp R., and Widgerson A 1985." A fast parallel algorithm for the maximal independent set problem". J. Assoc. for Computing Machinery, 32(4):762--773.
[9]
Kothapalli, K., Onus, M., Scheideler, C., and Schindelhauer. 2006. "Distributed coloring in Õ(√logn)-bits". In Proc. of the International Parallel and Distirbuted Processing Symposium (IPDPS).
[10]
Kuhn F. and Wattenhofer R. 2006. "On the complexity of distributed graph coloring", 25th Ann ACM Symp Princ Distrib Comput. (PODC), ACM Press, 7--15
[11]
Kuhn F., Moscibroda T., and Wattenhofer R. 2006." The price of being near-sighted". In Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA).
[12]
Leith, D. J, and Clifford P. 2006. "Convergence of distributed learing algorithms for optimal wireless channel allocation", In IEE CDC. Pages 2980--2985
[13]
Linial N. 1992. "Locality in distributed graph algorithms", SIAM J. on Computing 20 n. 1, 193--201.
[14]
Luby M. 1985. "A simple parallel algorithm for the maximal independent set problem". Proc. of ACM Symposium on Theory of Computing, 1--10.
[15]
Malone, D., Clifford P., Reid D. and Leith D. 2007. "Experimental implementation of optimal WLAN channel selection without communication". In IEEE DySPAN, 316--319
[16]
Madhav V. Marathe, Alessandro Panconesi, Larry D. Risinger Jr. 2004. "An experimental study of a simple, distributed edge-coloring algorithm". ACM Journal of Experimental Algorithmics 9.
[17]
Ramanathan S. 1999. "A unified framework and algorithm for channel assignment in wireless networks". Wireless Networks, 5:81--94
[18]
Roberts F. S. 2001. "Some applications of graph theory", in: Sungpyo Hong, et al., Combinatorial and computational mathematics (World Scientific Pub. Co.,).
[19]
Schneider J., Wattenhofer R. 2008. "log-star distributed maximal independent set algorithm for growth-bounded graphs, Annual ACM Symposium on Principles of Distributed Computing", Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, 35--44
Index Terms
- Randomized distributed algorithm for vertex coloring
Recommendations
Parity vertex coloring of outerplane graphs
A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c , the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G ...
Polynomial Cases for the Vertex Coloring Problem
The computational complexity of the Vertex Coloring problem is known for all hereditary classes of graphs defined by forbidding two connected five-vertex induced subgraphs, except for seven cases. We prove the polynomial-time solvability of four of ...
Graphs with multiplicative vertex-coloring 2-edge-weightings
A k-weighting w of a graph is an assignment of an integer weight $$w(e)\in \{1,...k\}$$w(e)ź{1,...k} to each edge e. Such an edge weighting induces a vertex coloring c defined by $$c(v)=\mathop {\displaystyle {\prod }}\limits _{v\in e}w(e).$$c(v)=źvźew(...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2010 ACM.
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]
Sponsors
- UNITECH: Unitech Engineers, India
- AICTE: All India Council for Technical Education
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 February 2010
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ICWET '10
Sponsor:
- UNITECH
- AICTE
ICWET '10: International Conference and Workshop on Emerging Trends in Technology
February 26 - 27, 2010
Maharashtra, Mumbai, India
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 122Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in