Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

被引：4
作者：
Lin, Ching-Chi
Chang, Gerard J. [1 ]
Chen, Gen-Huey
机构：
[1] Natl Taiwan Univ, Dept Math, Taipei 10617, Taiwan
[2] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei 10617, Taiwan
来源：
DISCRETE MATHEMATICS | 2007年 / 307卷 / 02期
关键词：
algorithm; circular-arc graph; directed path graph; interval graph; locally connected spanning tree; proper circular-arc graph; strongly chordal graph;
D O I：
10.1016/j.disc.2006.06.026
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v is an element of V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：208 / 215
页数：8
相关论文
共 50 条
[21]   Some optimal parallel algorithms on interval and circular-arc graphs [J].
Hsu, FR ;
Shan, MK ;
Chao, HS ;
Lee, RCT .
JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2005, 21 (03) :627-642
[22]   A Simpler Linear-Time Recognition of Circular-Arc Graphs [J].
Kaplan, Haim ;
Nussbaum, Yahav .
ALGORITHMICA, 2011, 61 (03) :694-737
[23]   Algorithms for generating maximum weight independent sets in circle graphs, circular-arc overlap graphs, and spider graphs [J].
Taki, M ;
Hatakenaka, H ;
Kashiwabara, T .
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1999, E82A (08) :1636-1640
[24]   A Simpler Linear-Time Recognition of Circular-Arc Graphs [J].
Haim Kaplan ;
Yahav Nussbaum .
Algorithmica, 2011, 61 :694-737
[25]   Computing K-Terminal Reliability of Circular-Arc Graphs [J].
Chen, Chien-Min ;
Lin, Min-Sheng .
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2016, E99D (12) :3047-3052
[26]   A linear-time algorithm for paired-domination on circular-arc graphs [J].
Lin, Ching-Chi ;
Tu, Hai-Lun .
THEORETICAL COMPUTER SCIENCE, 2015, 591 :99-105
[27]   Hadwiger's conjecture for proper circular arc graphs [J].
Belkale, Naveen ;
Chandran, L. Sunil .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (04) :946-956
[28]   Odd twists on strongly chordal graphs [J].
McKee, Terry A. .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2019, 11 (03)
[29]   Rainbow domination and related problems on strongly chordal graphs [J].
Chang, Gerard J. ;
Li, Bo-Jr ;
Wu, Jiaojiao .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) :1395-1401
[30]   Broadcast domination and multipacking in strongly chordal graphs [J].
Brewster, Richard C. ;
MacGillivray, Gary ;
Yang, Feiran .
DISCRETE APPLIED MATHEMATICS, 2019, 261 :108-118
12345