An Exact Parallel Algorithm for the Radio k-coloring Problem

For a positive integer k, a radio k-coloring of a simple connected graph G = (V (G), E(G)) is a mapping | f(u) - f(v)| ≥ k +1-d (u , v ) such that f :V (G)→{0,1, 2,...} for each pair of distinct vertices u and v of G, where d(u, v) is the distance between u and v in G. The span of a radio k-coloring f, rck(f), is the maximum integer it assigns to some vertex of G. The radio k-chromatic number, rck(G) of G is min{rck(f)}, where the minimum is taken over all radio k-colorings f of G. If k is the diameter of G, then rck(G) is known as the radio number of G. In this work, we propose four algorithms (two serial algorithms and their parallel versions) which related to the radio k-coloring problem. One of them is an approximate algorithm that determines an upper bound of the radio number of a given graph. The other is an exact algorithm which finds the radio number of a graph G. The approximate algorithm is a polynomial time algorithm while the exact algorithm is an exponential time algorithm. The parallel algorithms are parallelized using the Message Passing Interface (MPI) standard. The experimental results prove the ability of the proposed algorithms to achieve a speedup 7 for 8 processors.