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

DOI10.1007/S00453-012-9641-7zbMATH Open1263.05014OpenAlexW2002536646MaRDI QIDQ1950396FDOQ1950396

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

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

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)

Cites Work

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

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)