Minimum Vertex Ranking Spanning Tree Problem on Permutation Graphs

摘要

The minimum vertex ranking spanning tree problem on graph G is to find a spanning tree T of G such that the minimum vertex ranking of T is minimum among all possible spanning trees of G. In this paper, we propose a linear-time algorithm for this problem on permutation graphs. It improves a previous result that runs in O(n~3) time where n is the number of vertices in the input graph.