|
|||||
|
|
A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs |
|
| Authors: | Ching-Chi Lin Gen-Huey Chen Gerard J Chang |
| Affiliation: | 1. Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, 20224, Taiwan 2. Department of Computer Science and Information Engineering, National Taiwan University, Taipei, 10617, Taiwan 3. Department of Mathematics, National Taiwan University, Taipei, 10617, Taiwan 4. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei, 10617, Taiwan 5. National Center for Theoretical Sciences, Taipei Office, Taipei, 10617, Taiwan |
| 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |