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 条
  • [31] Parameterized Approximations for the Minimum Diameter Vertex-Weighted Steiner Tree Problem in Graphs with Parameterized Weights
    Ding, Wei
    Chen, Guangting
    Qiu, Ke
    Zhou, Yu
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2024,
  • [32] An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
    Honma, Hirotoshi
    Honma, Saki
    Masuyama, Shigeru
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2009, E92D (02) : 141 - 148
  • [33] Two heuristics for the capacitated minimum spanning tree problem with time windows
    Kritikos, Manolis N.
    Ioannou, George
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2019, 70 (04) : 555 - 567
  • [34] Competitive Decision Algorithm for the Rooted Delay-constrained Minimum Spanning Tree
    Xiong, Xiaohua
    Chen, Xuemin
    Ning, Aibing
    PROCEEDINGS OF THE 2013 THE INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND SOFTWARE ENGINEERING (ICAISE 2013), 2013, 37 : 82 - 86
  • [35] A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
    Silvestri, Selene
    Laporte, Gilbert
    Cerulli, Raffaele
    COMPUTERS & OPERATIONS RESEARCH, 2017, 81 : 322 - 332
  • [36] A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem
    Kavita Singh
    Shyam Sundar
    Soft Computing, 2020, 24 : 2169 - 2186
  • [37] Learning Collective Behavior of Social Media using Minimum Spanning Tree Algorithm
    Minal, Magare G.
    Patil, D. R.
    2015 2ND INTERNATIONAL CONFERENCE ON ELECTRONICS AND COMMUNICATION SYSTEMS (ICECS), 2015, : 461 - 464
  • [38] A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem
    Singh, Kavita
    Sundar, Shyam
    SOFT COMPUTING, 2020, 24 (03) : 2169 - 2186
  • [39] Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
    Gimadi E.K.
    Shin E.Y.
    Journal of Applied and Industrial Mathematics, 2015, 9 (04) : 480 - 488
  • [40] An optimal algorithm for finding depth-first spanning tree on permutation graphs
    Sukumar Mondal
    Madhumangal Pal
    Tapan K. Pal
    Korean Journal of Computational & Applied Mathematics, 1999, 6 (3) : 493 - 500
12345