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 条
  • [1] 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
  • [2] Hardness Results of Connected Power Domination for Bipartite Graphs and Chordal Graphs
    Goyal, Pooja
    Panda, B. S.
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2024, 35 (06) : 669 - 703
  • [3] Hardness Results of Connected Power Domination for Bipartite Graphs and Chordal Graphs
    Goyal, Pooja
    Panda, B. S.
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021, 2021, 13135 : 653 - 667
  • [4] Recognition of chordal graphs and cographs which are Cover-Incomparability graphs
    Anil, Arun
    Changat, Manoj
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2024, 26 (03): : 1 - 17
  • [5] A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
    Calamoneri, Tiziana
    Dell'Orefice, Matteo
    Monti, Angelo
    THEORETICAL COMPUTER SCIENCE, 2019, 764 : 2 - 14
  • [6] Hop Domination in Chordal Bipartite Graphs
    Henning, Michael A.
    Pal, Saikat
    Pradhan, D.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (03) : 825 - 840
  • [7] Injective coloring of some subclasses of bipartite graphs and chordal graphs
    Panda, B. S.
    Priyamvada
    DISCRETE APPLIED MATHEMATICS, 2021, 291 : 68 - 87
  • [8] Minimum Spanning Trees in Temporal Graphs
    Huang, Silu
    Fu, Ada Wai-Chee
    Liu, Ruifeng
    SIGMOD'15: PROCEEDINGS OF THE 2015 ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2015, : 419 - 430
  • [9] The number of spanning trees in Kn-Complements of quasi-threshold graphs
    Nikolopoulos, SD
    Papadopoulos, C
    GRAPHS AND COMBINATORICS, 2004, 20 (03) : 383 - 397
  • [10] 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
1234