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 条
  • [21] Optimal Independent Spanning Trees on Odd Graphs
    Jong-Seok Kim
    Hyeong-Ok Lee
    Eddie Cheng
    László Lipták
    The Journal of Supercomputing, 2011, 56 : 212 - 225
  • [22] How to Use Spanning Trees to Navigate in Graphs
    Feodor F. Dragan
    Yang Xiang
    Algorithmica, 2013, 66 : 479 - 511
  • [23] Enumeration of spanning trees in the sequence of Durer graphs
    Li, Shixing
    OPEN MATHEMATICS, 2017, 15 : 1591 - 1598
  • [24] How to Use Spanning Trees to Navigate in Graphs
    Dragan, Feodor F.
    Xiang, Yang
    ALGORITHMICA, 2013, 66 (03) : 479 - 511
  • [25] COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS
    Pradhan, D.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (03)
  • [26] Computing a minimum outer-connected dominating set for the class of chordal graphs
    Keil, J. Mark
    Pradhan, D.
    INFORMATION PROCESSING LETTERS, 2013, 113 (14-16) : 552 - 561
  • [27] Variations of the maximum leaf spanning tree problem for bipartite graphs
    Li, PC
    Toulouse, A
    INFORMATION PROCESSING LETTERS, 2006, 97 (04) : 129 - 132
  • [28] Counting Spanning Trees in Graphs Using Modular Decomposition
    Nikolopoulos, Stavros D.
    Palios, Leonidas
    Papadopoulos, Charis
    WALCOM: ALGORITHMS AND COMPUTATION, 2011, 6552 : 202 - +
  • [29] Epicenter of random epidemic spanning trees on finite graphs*
    Figueiredo, Daniel R.
    Iacobelli, Giulio
    MATHEMATICAL MODELLING OF NATURAL PHENOMENA, 2023, 18
  • [30] Full degree spanning trees in random regular graphs
    Acquaviva, Sarah
    Bal, Deepak
    DISCRETE APPLIED MATHEMATICS, 2024, 353 : 85 - 93
1234