A SELF-STABILIZING ALGORITHM FOR EDGE-COLORING OF GRAPHS

摘要

We discuss the edge-coloring problem in a distributed model. We give a self-stabilizing algorithm for coloring the edges of a graph G with 2Δ — 1 colors, which runs in O(Δm) moves, where m is the number of edges and Δ denotes the maximum vertex degree of G. Our algorithm is based on Hsu-Huang's algorithm for maximal matching.