A polynomial time algorithm for obtaining a minimum vertex ranking spanning tree in outerplanar graphs

Shin Ichi Nakayama, Shigeru Masuyama

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.

Original languageEnglish
Pages (from-to)2357-2363
Number of pages7
JournalIEICE Transactions on Information and Systems
VolumeE89-D
Issue number8
DOIs
Publication statusPublished - Aug 2006

    Fingerprint

Keywords

  • Algorithm
  • Outerplanar graph
  • Spanning tree
  • Vertex ranking

Cite this