A linear-time algorithm to find independent spanning trees in maximal planar graphs

被引：0
|
作者：
Nagai, S [1 ]
Nakano, S [1 ]
机构：
[1] Gunma Univ, Fac Engn, Dept Comp Sci, Kiryu, Gumma 3768515, Japan
来源：
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2001年 / E84A卷 / 05期
关键词：
graph; algorithm; independent spanning trees;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Given a graph G: a designated vertex r and a natural number k, we wish to iind k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex rr, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find I; independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.
引用
收藏
页码：1102 / 1109
页数：8
相关论文
共 50 条
  • [1] A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs
    Ching-Chi Lin
    Gen-Huey Chen
    Gerard J. Chang
    Algorithmica, 2013, 66 : 369 - 396
  • [2] A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs
    Lin, Ching-Chi
    Chen, Gen-Huey
    Chang, Gerard J.
    ALGORITHMICA, 2013, 66 (02) : 369 - 396
  • [3] A linear-time algorithm for clique-coloring planar graphs
    Liang, Zuosong
    Shan, Erfang
    Xing, Huiyu
    Bai, Chunsong
    OPERATIONS RESEARCH LETTERS, 2019, 47 (04) : 241 - 243
  • [4] Linear-time algorithm for sliding tokens on trees
    Demaine, Erik D.
    Demaine, Martin L.
    Fox-Epstein, Eli
    Hoang, Duc A.
    Ito, Takehiro
    Ono, Hirotaka
    Otachic, Yota
    Uehara, Ryuhei
    Yamada, Takeshi
    THEORETICAL COMPUTER SCIENCE, 2015, 600 : 132 - 142
  • [5] 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
  • [6] A Linear-Time Algorithm to Find a Separator in a Graph Excluding a Minor
    Reed, Bruce
    Wood, David R.
    ACM TRANSACTIONS ON ALGORITHMS, 2009, 5 (04)
  • [7] New Linear-Time Algorithms for Edge-Coloring Planar Graphs
    Richard Cole
    Łukasz Kowalik
    Algorithmica, 2008, 50 : 351 - 368
  • [8] New linear-time algorithms for edge-coloring planar graphs
    Cole, Richard
    Kowalik, Lukasz
    ALGORITHMICA, 2008, 50 (03) : 351 - 368
  • [9] A LINEAR-TIME ALGORITHM FOR ISOMORPHISM OF GRAPHS OF BOUNDED AVERAGE GENUS
    CHEN, JN
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (04) : 614 - 631
  • [10] Independent spanning trees of product graphs and their construction
    Obokata, K
    Iwasaki, Y
    Bao, F
    Igarashi, Y
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1996, E79A (11) : 1894 - 1903
12345