research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleDistributed Game-Theoretic Vertex Coloring
Bibtex cite IDRACTI-RU1-2010-46
Booktitle 14th International Conference On Principles Of Distributed Systems
Year published 2010
Month December
Volume 6490/2010
Pages 103-118
DOI 10.1007/978-3-642-17653-1_9
We exploit the game-theoretic ideas presented in [12] to study the vertex coloring problem in a distributed setting. The vertices of the graph are seen as players in a suitably defined strategic game, where each player has to choose some color, and the payoff of a vertex is the total number of players that have chosen the same color as its own. We extend here the results of [12] by showing that, if any subset of nonneighboring vertices perform a selfish step (i.e., change their colors in order to increase their payoffs) in parallel, then a (Nash equilibrium) proper coloring, using a number of colors within several known upper bounds on the chromatic number, can still be reached in polynomial time. We also present an implementation of the distributed algorithm in wireless networks of tiny devices and evaluate the performance in simulated and experimental environments. The performance analysis indicates that it is the first practically implementable distributed algorithm.
Chatzigiannakis, Ioannis
Koninis, Christos
Panagopoulou, Panagiota
Spirakis, Paul
distributed game.pdf (main file)
Publication ID815