A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

被引：0
|
作者：
Ching-Chi Lin
Gen-Huey Chen
Gerard J. Chang
机构：
[1] National Taiwan Ocean University,Department of Computer Science and Engineering
[2] National Taiwan University,Department of Computer Science and Information Engineering
[3] National Taiwan University,Department of Mathematics
[4] National Taiwan University,Taida Institute for Mathematical Sciences
[5] National Center for Theoretical Sciences,undefined
[6] Taipei Office,undefined
来源：
Algorithmica | 2013年 / 66卷
关键词：
Algorithm; Circular-arc graph; Interval graph; Locally connected spanning tree; Spanning tree;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.
引用
收藏
页码：369 / 396
页数：27
相关论文
共 29 条
  • [1] 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
  • [2] Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
    Lin, Ching-Chi
    Chang, Gerard J.
    Chen, Gen-Huey
    DISCRETE MATHEMATICS, 2007, 307 (02) : 208 - 215
  • [3] A linear-time algorithm for paired-domination on circular-arc graphs
    Lin, Ching-Chi
    Tu, Hai-Lun
    THEORETICAL COMPUTER SCIENCE, 2015, 591 : 99 - 105
  • [4] Linear-Time Recognition of Circular-Arc Graphs
    Ross M. McConnell
    Algorithmica , 2003, 37 : 93 - 147
  • [5] Linear-time recognition of circular-arc graphs
    McConnell, RM
    ALGORITHMICA, 2003, 37 (02) : 93 - 147
  • [6] A Simpler Linear-Time Recognition of Circular-Arc Graphs
    Kaplan, Haim
    Nussbaum, Yahav
    ALGORITHMICA, 2011, 61 (03) : 694 - 737
  • [7] A Simpler Linear-Time Recognition of Circular-Arc Graphs
    Haim Kaplan
    Yahav Nussbaum
    Algorithmica, 2011, 61 : 694 - 737
  • [8] A linear-time algorithm for clique-coloring problem in circular-arc graphs
    Zuosong Liang
    Erfang Shan
    Yuzhong Zhang
    Journal of Combinatorial Optimization, 2017, 33 : 147 - 155
  • [9] A linear-time algorithm for clique-coloring problem in circular-arc graphs
    Liang, Zuosong
    Shan, Erfang
    Zhang, Yuzhong
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (01) : 147 - 155
  • [10] 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
123