S.-T. Huang and Y.-H. Wang (Taiwan)
self-stabilization, distributed algorithm, acyclic colorings.
This paper proposes two self-stabilizing algorithms for acyclic colorings of graphs. An acyclic coloring of a graph G is a coloring of the vertices of G such that the vertices with the same color in G induces an acyclic subgraph. The first algorithm we proposed needs 2 colors for a complete bipartite graph, or less than 1+D/2 colors for a general graph, where D is the degree of G. Both graphs must be acyclic oriented in advance. In some special acyclic orientation, it needs only 3 colors for a planar graph, or a K3,3-free or K5-free graph. The second algorithm we proposed is for a K4-free and rooted graph, and it needs only 2 colors.
Important Links:
Go Back
