Distributed greedy coloring is an interesting and intuitive variation of the standard coloring problem. Given an order among the colors, a coloring is said to be greedy if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighboring vertices must receive different colors. We consider the problems of Greedy Coloring and Largest First Coloring (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the (Δ + 1)-Coloring and Maximal Independent Set problems, with Δ being the maximum vertex degree in G
On the Complexity of Distributed Graph Coloring with Local Minimality Constraints
NAVARRA, Alfredo
2009
Abstract
Distributed greedy coloring is an interesting and intuitive variation of the standard coloring problem. Given an order among the colors, a coloring is said to be greedy if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighboring vertices must receive different colors. We consider the problems of Greedy Coloring and Largest First Coloring (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the (Δ + 1)-Coloring and Maximal Independent Set problems, with Δ being the maximum vertex degree in GI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
