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 条
[41]   Characterizing and computing the structure of clique intersections in strongly chordal graphs [J].
Nevries, Ragnar ;
Rosenke, Christian .
DISCRETE APPLIED MATHEMATICS, 2015, 181 :221-234
[42]   O(M-CENTER-DOT-N) ALGORITHMS FOR THE RECOGNITION AND ISOMORPHISM PROBLEMS ON CIRCULAR-ARC GRAPHS [J].
HSU, WL .
SIAM JOURNAL ON COMPUTING, 1995, 24 (03) :411-439
[43]   An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs [J].
Saha A. ;
Pal M. ;
Pal T.K. .
Journal of Applied Mathematics and Computing, 2005, 17 (1-2) :1-23
[44]   AN O(N2 LOG N) ALGORITHM FOR THE HAMILTONIAN CYCLE PROBLEM ON CIRCULAR-ARC GRAPHS [J].
SHIH, WK ;
CHERN, TC ;
HSU, WL .
SIAM JOURNAL ON COMPUTING, 1992, 21 (06) :1026-1046
[45]   COMPETITION GRAPHS OF STRONGLY CONNECTED AND HAMILTONIAN DIGRAPHS [J].
FRAUGHNAUGH, KF ;
LUNDGREN, JR ;
MERZ, SK ;
MAYBEE, JS ;
PULLMAN, NJ .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (02) :179-185
[46]   Full degree spanning trees in random regular graphs [J].
Acquaviva, Sarah ;
Bal, Deepak .
DISCRETE APPLIED MATHEMATICS, 2024, 353 :85-93
[47]   On minimum spanning trees for random Euclidean bipartite graphs [J].
Correddu, Mario ;
Trevisan, Dario .
COMBINATORICS PROBABILITY AND COMPUTING, 2024, 33 (03) :319-350
[48]   Minimum Strongly Connected Subgraph Collection in Dynamic Graphs [J].
Chen, Xin ;
Shi, Jieming ;
Peng, You ;
Lin, Wenqing ;
Wang, Sibo ;
Zhang, Wenjie .
PROCEEDINGS OF THE VLDB ENDOWMENT, 2024, 17 (06) :1324-1336
[49]   Activity preserving bijections between spanning trees and orientations in graphs [J].
Gioan, E ;
Vergnas, ML .
DISCRETE MATHEMATICS, 2005, 298 (1-3) :169-188
[50]   Completely Independent Spanning Trees in the Line Graphs of Torus Networks [J].
Bian, Qingrong ;
Cheng, Baolei ;
Fan, Jianxi ;
Pan, Zhiyong .
ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2021, PT III, 2022, 13157 :540-553
12345