Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

被引：2
|
作者：
Panda, B. S. [1 ]
Pradhan, D. [1 ]
机构：
[1] Indian Inst Technol Delhi, Comp Sci & Applicat Grp, Dept Math, New Delhi 110016, India
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 23期
关键词：
Algorithms; Graph algorithms; Locally connected spanning tree; NP-complete; NETWORKS; 2-TREES;
D O I：
10.1016/j.ipl.2010.09.008
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A spanning tree T of a graph G = (V, E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v is an element of V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：1067 / 1073
页数：7
相关论文
共 40 条
  • [31] On the k-Hop Domination Numbers of Spanning Trees of Unicyclic Graphs
    Jindaluang, Wattana
    Juneam, Nopadon
    THAI JOURNAL OF MATHEMATICS, 2021, 19 (01): : 9 - 17
  • [32] Solving the all-pairs-shortest-length problem on chordal bipartite graphs
    Ho, CW
    Chang, JM
    INFORMATION PROCESSING LETTERS, 1999, 69 (02) : 87 - 93
  • [33] Hamilton cycles in sparse locally connected graphs
    van Aardt, Susan A.
    Burger, Alewyn P.
    Frick, Marietjie
    Thomassen, Carsten
    de Wet, Johan P.
    DISCRETE APPLIED MATHEMATICS, 2019, 257 : 276 - 288
  • [34] A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs
    Ma Jun
    Ma Shaohan
    Kazuo Iwama
    Gu Qianping
    Acta Mathematicae Applicatae Sinica, 1999, 15 (3) : 303 - 309
  • [35] The Degree-Preserving Spanning Tree Problem in Strongly Chordal and Directed Path Graphs
    Lin, Ching-Chi
    Chang, Gerard J.
    Chen, Gen-Huey
    NETWORKS, 2010, 56 (03) : 183 - 187
  • [36] Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs
    Lin, Chung-Ming
    Tsai, Yin Te
    Tang, Chuan Yi
    INFORMATION PROCESSING LETTERS, 2006, 99 (02) : 64 - 67
  • [37] A new algorithm for finding minimum spanning trees with undirected neutrosophic graphs
    Dey, Arindam
    Broumi, Said
    Le Hoang Son
    Bakali, Assia
    Talea, Mohamed
    Smarandache, Florentin
    GRANULAR COMPUTING, 2019, 4 (01) : 63 - 69
  • [38] Identifying the Most Connected Vertices in Hidden Bipartite Graphs Using Group Testing
    Wang, Jianguo
    Lo, Eric
    Yiu, Man Lung
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2013, 25 (10) : 2245 - 2256
  • [39] Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs
    Chen, Qing
    Lachish, Oded
    Helmer, Sven
    Bohlen, Michael H.
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2022, 15 (11): : 3263 - 3276
  • [40] Experimental analysis of algorithms for updating minimum spanning trees on graphs subject to changes on edge weights
    Ribeiro, Celso C.
    Toso, Rodrigo F.
    EXPERIMENTAL ALGORITHMS, PROCEEDINGS, 2007, 4525 : 393 - +
1234