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

被引：2
|
作者：
Nakayama, Shin-ichi [1 ]
Masuyama, Shigeru
机构：
[1] Univ Tokushima, Fac Integrated Arts & Sci, Dept Math Sci, Tokushima 7708502, Japan
[2] Toyohashi Univ Technol, Dept Knowledge Based Informat Engn, Toyohashi, Aichi 4418580, Japan
来源：
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2006年 / E89D卷 / 08期
关键词：
algorithm; vertex ranking; spanning tree; outerplanar graph;
D O I：
10.1093/ietisy/e89-d.8.2357
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：2357 / 2363
页数：7
相关论文
共 50 条
  • [1] An algorithm for solving the minimum vertex ranking spanning tree problem on interval graphs
    Nakayama, SI
    Masuyama, S
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2003, E86A (05): : 1019 - 1026
  • [2] An algorithm for solving the minimum vertex-ranking spanning tree problem on series-parallel graphs
    Kashem, Md. Abul
    Hasan, Chowdhury Sharif
    Bhattacharjee, Anupam
    ICECE 2006: PROCEEDINGS OF THE 4TH INTERNATIONAL CONFERENCE ON ELECTRICAL AND COMPUTER ENGINEERING, 2006, : 328 - +
  • [3] A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Outerplanar Graphs
    Nakayama, Shin-ichi
    Masuyama, Shigeru
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2017, E100D (03) : 434 - 443
  • [4] Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
    Mezzini, Mauro
    THEORETICAL COMPUTER SCIENCE, 2018, 745 : 63 - 74
  • [5] Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem
    Miyata, Keizo
    Masuyama, Shigeru
    Nakayama, Shin-ichi
    Zhao, Liang
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (16) : 2402 - 2410
  • [6] A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs
    Li, Xingfu
    Feng, Haodi
    Jiang, Haitao
    Zhu, Binhai
    FRONTIERS IN ALGORITHMICS, FAW 2016, 2016, 9711 : 92 - 101
  • [7] NP-Completeness of the minimum edge-ranking spanning tree problem on series-parallel graphs
    Arefin, Ahmed Shamsul
    Mia, Md. Abul Kashem
    PROCEEDINGS OF 10TH INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION TECHNOLOGY (ICCIT 2007), 2007, : 13 - 16
  • [8] A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc Graphs
    Nakayama, Shin-ichi
    Masuyama, Shigeru
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2022, E105D (08) : 1373 - 1382
  • [9] A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
    Yao, Guohui
    Zhu, Daming
    Li, Hengwu
    Ma, Shaohan
    DISCRETE MATHEMATICS, 2008, 308 (17) : 3951 - 3959
  • [10] A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set VNT on Series-Parallel Graphs
    Nakayama, Shin-ichi
    Masuyama, Shigeru
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2019, E102D (04) : 826 - 835
12345