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 log N)time with high probability for generic graphs, when the number of available colors is greater than Δ, the maximum degree of the graph, and in O(N log N) time if Δ=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.
Fast, Responsive Decentralized Graph Coloring / Checco, A.; Leith, D. J.. - In: IEEE-ACM TRANSACTIONS ON NETWORKING. - ISSN 1063-6692. - 25:6(2017), pp. 3628-3640. [10.1109/TNET.2017.2751544]
Fast, Responsive Decentralized Graph Coloring
Checco A.;
2017
Abstract
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 log N)time with high probability for generic graphs, when the number of available colors is greater than Δ, the maximum degree of the graph, and in O(N log N) time if Δ=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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
