.png){kind=icon}
.png){kind=icon}
Return
Fast, Responsive Decentralized Graph Coloring
.png){kind=icon}
OA
AI
DOI：10.1109/TNET.2017.2751544.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Graph theory
network theory (graphs)
wireless networks
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K