A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
From MaRDI portal
Publication:1950396
DOI10.1007/s00453-012-9641-7zbMath1263.05014OpenAlexW2002536646MaRDI QIDQ1950396
Ching-Chi Lin, Gen-Huey Chen, Gerard Jennhwa Chang
Publication date: 13 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9641-7
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
- Characterizations of strongly chordal graphs
- Linear time algorithms on circular-arc graphs
- An optimal algorithm for finding dominating cycles in circular-arc graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- \(k\) best cuts for circular-arc graphs
- On spanning 2-trees in a graph
- The complexity of the locally connected spanning tree problem
- Linear-time recognition of circular-arc graphs
- Algorithmic graph theory and perfect graphs
- Minimum Cuts for Circular-Arc Graphs
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Stability in circular arc graphs
- Three Partition Refinement Algorithms
- An Efficient Test for Circular-Arc Graphs
- Networks immune to isolated failures
- Efficient algorithms for interval graphs and circular-arc graphs
- Networks immune to isolated line failures
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Independent Sets in Circular-Arc Graphs
This page was built for publication: A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
