Abstract:
In this thesis we present an efficient parallel algorithm for solving the generalized
vertex-coloring (l-vertex-coloring) problem on partial k-trees. Let l be a positive
integer, and let G be a graph with nonnegative integer weights on edges. Theil the
optimal l-vertex-coloring problem on G is an assignment of colors to the vertices of G
in such a way that any two vertices u and v in G get different colors if the distance
between u and v is at most l and the number of colors used is as small as possible. The
l-vertex-coloring problem has applications in various scheduling problems. In this
paper we give a parallel algorithm to find an l-vertex-coloring of a partial k-tree G
with the minimum number of colors. Our algorithm takes O(logz n) parallel time
using O(a x (t + 2)6a('+1) X n + n') operations on the common CRCW PRAM model,
where n is the number of vertices in G and a is the number of colors in the color-set.
The previously known best algorithm takes O(log2n) parallel time using
O(n(a + 1)""Hx"" + n') operations on the common CRCW PRAM.
