期刊
IEEE-ACM TRANSACTIONS ON NETWORKING
卷 25, 期 6, 页码 3628-3640出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2017.2751544
关键词
Graph theory; network theory (graphs); wireless networks
类别
资金
- Science Foundation Ireland [11/PI/1177]
Graph coloring problem arises in numerous networking applications. We solve it in a fully decentralized way (i. 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 O(N logN) 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 O(logN) time if Delta = 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据