Two Edge Coloring Algorithms Using a Simple Matching Discovery Automata
J. Paul Daigle, Sushil K. Prasad · 2012
We here present two probabilistic edge coloring algorithms for a message passing model of distributed computing. The algorithms use a simple automata for finding a matching on a graph to produce the colorings. Our first algorithm for edge coloring finds an edge coloring of a graph which is guaranteed to use no more than 2Δ - 1 colors and completes in O(Δ) communication rounds using only one hop information, where Δ is the greatest degree of the graph. Our second algorithm finds a strong edge coloring of a symmetric digraph in O(Δ) communication rounds, using only one hop information.