Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
type: Item
instance of: scholarly article
title: Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
zbMATH Open document ID: 1119.05102
author: Ching-Chi Lin
author: Gen-Huey Chen
author: Gerard Jennhwa Chang
published in: Discrete Mathematics
publication date: 2007-02-13T00:00:00Z
review text: A spanning tree \(T\) of a graph \(G=(V,E)\) is locally connected if for all \(v \in V\) the subgraph of \(G\) induced by \(N_T(v)\) is connected. \textit{L. Cai} [Discrete Appl. Math. 131, 63--75 (2003; Zbl 1022.05079)] showed that it is NP-complete to decide whether a graph has a locally connected spanning tree. Restricted to strongly chordal graphs and circular-arc graphs this problem becomes solvable in linear time, if a simple elimination ordering or arc-intersection model is provided with the input.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5124987
zbMATH Keywords: algorithm
zbMATH Keywords: circular-arc graph
zbMATH Keywords: directed path graph
zbMATH Keywords: interval graph
zbMATH Keywords: locally connected spanning tree
zbMATH Keywords: proper circular-arc graph
zbMATH Keywords: strongly chordal graph
MaRDI profile type: Publication
full work available at URL: j.disc.2006.06.026
OpenAlex ID: W2037551081
cites work: Characterizations of totally balanced matrices
cites work: On spanning 2-trees in a graph
cites work: The complexity of the locally connected spanning tree problem
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Characterizations of strongly chordal graphs
cites work: Networks immune to isolated failures
cites work: Networks immune to isolated line failures
cites work: Q3328583
cites work: Totally-Balanced and Greedy Matrices
cites work: Doubly Lexical Orderings of Matrices
cites work: Linear-time recognition of circular-arc graphs
cites work: Three Partition Refinement Algorithms
cites work: Doubly lexical ordering of dense 0--1 matrices
cites work: Steiner trees, partial 2–trees, and minimum IFI networks
DOI: 10.1016/J.DISC.2006.06.026
description: scientific article; zbMATH DE number 5124987