Parallel algorithm for generalized vertex-colorings of partial K-trees

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.