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

Shin-ichi NAKAYAMA  Shigeru MASUYAMA  

Publication
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: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithm,  vertex ranking,  spanning tree,  interval graph,  

Full Text: PDF>>
Buy this Article




Summary: 
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.