A parallel algorithm for generating ideal IC-colorings of cycles

摘要

For a given graph G with the vertex set V(G), a coloring f:V(G)→N produces α where α=∑u∈V(H)f(u) for some connected subgraph H of G ∑u∈V(H)f(u)=0ifV(H)=∅. The coloring f is an IC-coloring of G if f produces each α∈{0,1,…,S(f)}, where S(f) is the maximum number that can be produced by f. The IC-index M(G) of the graph G is the number maxS(g)|gisanIC-coloringofG. An IC-coloring f is ideal if S(f) is equal to the number of connected subgraph of G. In this paper, a sound and complete parallel algorithm based on the branch and bound technique is proposed to generate ideal IC-colorings of cycles, Cn. Experiments identified 118 ideal IC-colorings of Cn when 2