An Algorithm for Solving the Minimum Vertex-Ranking Spanning Tree Problem on Series-Parallel Graphs

摘要

A vertex-ranking of a graph G is a labeling of the vertices of G with positive integers such that every path between two vertices with the same label i contains a vertex with label j > i. The minimum vertex-ranking spanning tree problem is to find a spanning tree of a graph G whose vertex-ranking needs least number of labels. In this paper, we present an algorithm to solve the minimum vertex-ranking spanning tree problem on a series-parallel graph G in O(n⁵ log⁴ n) time, where n is the number of vertices in G.