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.
