A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs

24 References
  • NAKAYAMA Shin-ichi
    Department of Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Tokushima
  • MASUYAMA Shigeru
    Department of Knowledge-Based Information Engineering, Toyohashi University of Technology

Search this article

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.

Journal

References(24)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1570009752661185152
  • NII Article ID
    110007538522
  • NII Book ID
    AA10826272
  • ISSN
    09168532
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top