Algorithm for solving minimum vertex-ranking spanning tree problem on partial K-trees

Abstract

This thesis introduces an algorithm for finding a minimum vertex-ranking spanning tree of a partial k-tree. A vertex-ranking of a graph G is a labeling of its vertices with positive integers such that every path between two vertices with the same label i contains an intermediate vertex with label j > i. A vertex-ranking is optimal if least number of ranks are used to rank the graph. The minimum vertex-ranking spanning tree problem is to find a spanning tree of a graph G whose vertex-ranking is minimum. The minimum vertex-ranking spanning tree problem has received much attention because of growing number of applications such as scheduling the parallel assembly of a complex multi-part product from its components, VLSI layout design and join operation for query graphs in a relational database. Recently it has been proved that this problem is NP-hard for general graphs but the complexity class of the problem on partial k-trees is not known yet. In this thesis, a polynomial-time algorithm for finding a minimum vertex-ranking spanning tree of a partial k-tree is presented, where k is bounded by a constant.