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 条
  • [21] A Polynomial-Time Algorithm for Computing the Maximum Common Connected Edge Subgraph of Outerplanar Graphs of Bounded Degree
    Akutsu, Tatsuya
    Tamura, Takeyuki
    ALGORITHMS, 2013, 6 (01) : 119 - 135
  • [22] An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection
    Hassin, R
    Levin, A
    SIAM JOURNAL ON COMPUTING, 2004, 33 (02) : 261 - 268
  • [23] A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Interval Graphs
    Nakayama, Shin-ichi
    Masuyama, Shigeru
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2018, E101D (09): : 2235 - 2246
  • [24] Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
    Reed, Bruce
    Stein, Maya
    JOURNAL OF GRAPH THEORY, 2023, 102 (04) : 797 - 821
  • [25] Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
    Reed, Bruce
    Stein, Maya
    JOURNAL OF GRAPH THEORY, 2023, 102 (04) : 737 - 783
  • [26] Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty
    Mathwieser, Corinna
    Cela, Eranda
    NETWORKS, 2024, 83 (03) : 587 - 604
  • [27] The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
    Cardinal, Jean
    Demaine, Erik D.
    Fiorini, Samuel
    Joret, Gwenael
    Newman, Ilan
    Weimann, Oren
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 25 (01) : 19 - 46
  • [28] The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs
    Cardinal, Jean
    Demaine, Erik D.
    Fiorini, Samuel
    Joret, Gwenael
    Newman, Ilan
    Weimann, Oren
    INTERNET AND NETWORK ECONOMICS, PROCEEDINGS, 2009, 5929 : 125 - +
  • [29] The capacitated minimum spanning tree problem with arc time windows
    Kritikos, Manolis N.
    Ioannou, George
    EXPERT SYSTEMS WITH APPLICATIONS, 2021, 176
  • [30] An Exact Polynomial Algorithm for the Outerplanar Facility Location Problem with Improved Time Complexity
    Gimadi, Edward
    ANALYSIS OF IMAGES, SOCIAL NETWORKS AND TEXTS, AIST 2017, 2018, 10716 : 295 - 303
12345