An efficient algorithm l-vertex-coloring of partial k-trees

Abstract

This thesis presents an efficient algorithm for finding an optimal I-vertex-coloring of a partial k-tree. An I-vertex-coloring of a graph G is defined as follows: for a positive integer I and a graph G with non-negative integer weights on edges, a generalized vertexcoloring, called an I-vertex-coloring of G, is an assigmnent of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most I. A partial k-tree is a graph with tree-width bounded by a fixed integer k. An I-vertex-coloring is optimal if the number of colors used is as small as possible. The problem of finding an I-vertex-coloring of G plays an important role in meeting, examination and class scheduling, 4-coloring of maps with adjacent regions having different colors, allocation of registers to the CPU, etc. We present an G(n(l + 2)2a(k + l)aloga + n3 ) time algorithm to find an I-vertex-coloring of a partial k-tree G, where n is the number of vertices in G and a is size of the color-set. The previously • 22(.1:+1)(1+2)+1 3. known best algonthm takes G(n(a + I) + n ) time to find an optimal I-vertexcoloring of a partial k-tree.