Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
Resource
Discrete Mathematics 307 (2): 208-215
Journal
Discrete Mathematics
Journal Volume
307
Journal Issue
2
Pages
208-215
Date Issued
2007
Author(s)
Abstract
A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v ∈ V (G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively. © 2006 Elsevier B.V. All rights reserved.
Subjects
Algorithm; Circular-arc graph; Directed path graph; Interval graph; Locally connected spanning tree; Proper circular-arc graph; Strongly chordal graph
Other Subjects
Algorithms; Set theory; Circular arc graph; Directed path graph; Interval graph; Locally connected spanning tree; Proper circular arc graph; Strongly chordal graph; Trees (mathematics)
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
08.pdf
Size
24.37 KB
Format
Adobe PDF
Checksum
(MD5):f10d91111112f9ad28560b8b4414d263