학술논문
Fast, Responsive Decentralized Graph Coloring
Document Type
Periodical
Author
Source
IEEE/ACM Transactions on Networking IEEE/ACM Trans. Networking Networking, IEEE/ACM Transactions on. 25(6):3628-3640 Dec, 2017
Subject
Language
ISSN
1063-6692
1558-2566
1558-2566
Abstract
Graph coloring problem arises in numerous networking applications. We solve it in a fully decentralized way (ı.e., with no message passing). We propose a novel algorithm that is automatically responsive to topology changes, and we prove that it converges to a proper coloring in $ \mathrm {\mathcal {O}}(N\log {N})$ time with high probability for generic graphs, when the number of available colors is greater than $\Delta $ , the maximum degree of the graph, and in $ \mathrm {\mathcal {O}}(\log {N})$ time if $\Delta = \mathrm {\mathcal {O}}(1)$ . We believe the proof techniques used in this paper are of independent interest and provide new insight into the properties required to ensure fast convergence of decentralized algorithms.