A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs.
Journal
Algorithmica
Journal Volume
66
Journal Issue
2
Pages
369-396
Date Issued
2013
Author(s)
Abstract
Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists. © 2012 Springer Science+Business Media, LLC.
Type
journal article