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 条
[31]   Surjective L(2,1)-labeling of cycles and circular-arc graphs [J].
Amanathulla, Sk ;
Pal, Madhumangal .
JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2018, 35 (01) :739-748
[32]   A linear algorithm for maximum weight cliques in proper circular arc graphs [J].
Bhattacharya, B ;
Hell, P ;
Huang, J .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) :274-289
[33]   Spanning trees in randomly perturbed graphs [J].
Joos, Felix ;
Kim, Jaehoon .
RANDOM STRUCTURES & ALGORITHMS, 2020, 56 (01) :169-219
[34]   A linear-time algorithm for clique-coloring problem in circular-arc graphs [J].
Liang, Zuosong ;
Shan, Erfang ;
Zhang, Yuzhong .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (01) :147-155
[35]   A linear-time algorithm for clique-coloring problem in circular-arc graphs [J].
Zuosong Liang ;
Erfang Shan ;
Yuzhong Zhang .
Journal of Combinatorial Optimization, 2017, 33 :147-155
[36]   MAXCLIQUE AND UNIT DISK CHARACTERIZATIONS OF STRONGLY CHORDAL GRAPHS [J].
De Caria, Pablo ;
McKee, Terry A. .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (03) :593-602
[37]   Boxicity of Circular Arc Graphs [J].
Diptendu Bhowmick ;
L. Sunil Chandran .
Graphs and Combinatorics, 2011, 27 :769-783
[38]   Boxicity of Circular Arc Graphs [J].
Bhowmick, Diptendu ;
Chandran, L. Sunil .
GRAPHS AND COMBINATORICS, 2011, 27 (06) :769-783
[39]   Enumerating spanning and connected subsets in graphs and matroids [J].
Khachiyan, Leonid ;
Boros, Endre ;
Borys, Konrad ;
Elbassioni, Khaled ;
Gurvich, Vladimir ;
Makino, Kazuhisa .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 2007, 50 (04) :325-338
[40]   Random Spanning Trees and the Prediction of Weighted Graphs [J].
Cesa-Bianchi, Nicolo ;
Gentile, Claudio ;
Vitale, Fabio ;
Zappella, Giovanni .
JOURNAL OF MACHINE LEARNING RESEARCH, 2013, 14 :1251-1284
12345