부산대학교 도서관

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.