A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs

被引：0

作者：

Calamoneri, Tiziana ^{[1
]}

Dell'Orefice, Matteo ^{[1
]}

Monti, Angelo ^{[1
]}

机构：

[1] Sapienza Univ Rome, Comp Sci Dept, Rome, Italy

来源：

THEORETICAL COMPUTER SCIENCE | 2019年 / 764卷

关键词：

Locally connected spanning tree; Partial k trees; SC k-trees; 2-Trees; Chordal graphs; Planar graphs; K-TREES; COMPLEXITY;

D O I：

10.1016/j.tcs.2018.02.025

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected subgraph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a simple linear time algorithm that, given a maximal planar chordal graph, determines in linear time whether it contains an LCST or not, and produces one if it exists. We give an analogous result for the case when the input graph is a maximal outerplanar graph. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：2 / 14

页数：13

共 25 条

[1] Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
Panda, B. S.
Pradhan, D.
INFORMATION PROCESSING LETTERS, 2010, 110 (23) : 1067 - 1073
[2] The complexity of the locally connected spanning tree problem
Cai, LZ
DISCRETE APPLIED MATHEMATICS, 2003, 131 (01) : 63 - 75
[3] A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs
Ching-Chi Lin
Gen-Huey Chen
Gerard J. Chang
Algorithmica, 2013, 66 : 369 - 396
[4] 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
[5] 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
[6] A LINEAR ALGORITHM FOR THE GROUP PATH PROBLEM ON CHORDAL GRAPHS
ARIKATI, SR
PELED, UN
DISCRETE APPLIED MATHEMATICS, 1993, 44 (1-3) : 185 - 190
[7] A LINEAR-TIME ALGORITHM FOR ISOMORPHISM OF A SUBCLASS OF CHORDAL GRAPHS
VEERARAGHAVULU, NC
KUMAR, PS
MADHAVAN, CEV
INFORMATION PROCESSING LETTERS, 1992, 44 (01) : 45 - 49
[8] A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
Williams, JC
NETWORKS, 2002, 39 (01) : 53 - 60
[9] An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
Dragan, Feodor F.
INFORMATION PROCESSING LETTERS, 2020, 154
[10] A linear time algorithm for the arc disjoint menger problem in planar directed graphs
Brandes, U
Wagner, D
ALGORITHMICA, 2000, 28 (01) : 16 - 36

← 1 2 3 →