A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs

DOI10.1007/S00453-012-9641-7MaRDI QIDQ1950396zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

algorithminterval graphcircular-arc graphlocally connected spanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
• The complexity of the locally connected spanning tree problem
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph

Cites work

• Algorithmic graph theory and perfect graphs
• An Efficient Test for Circular-Arc Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• An optimal algorithm for finding dominating cycles in circular-arc graphs
• Characterizations of strongly chordal graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Independent Sets in Circular-Arc Graphs
• Linear time algorithms on circular-arc graphs
• Linear-time recognition of circular-arc graphs
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• Minimum Cuts for Circular-Arc Graphs
• Networks immune to isolated failures
• Networks immune to isolated line failures
• On spanning 2-trees in a graph
• Stability in circular arc graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The complexity of the locally connected spanning tree problem
• Three Partition Refinement Algorithms
• \(k\) best cuts for circular-arc graphs

Cited in

(4)

• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
• Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
• The complexity of the locally connected spanning tree problem
• Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

This page was built for publication: A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1950396)