An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs

Shin-ichi NAKAYAMA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.5   pp.1019-1026
Publication Date: 2003/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
algorithm,  vertex ranking,  spanning tree,  interval graph,  

Full Text: PDF(301.5KB)>>
Buy this Article

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.