A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
type: Item
instance of: scholarly article
title: A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
zbMATH Open document ID: 1263.05014
author: Ching-Chi Lin
author: Gen-Huey Chen
author: Gerard Jennhwa Chang
published in: Algorithmica
publication date: 2013-05-13T00:00:00Z
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6162398
zbMATH Keywords: algorithm
zbMATH Keywords: circular-arc graph
zbMATH Keywords: interval graph
zbMATH Keywords: locally connected spanning tree
MaRDI profile type: Publication
full work available at URL: s00453-012-9641-7
OpenAlex ID: W2002536646
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: On spanning 2-trees in a graph
cites work: The complexity of the locally connected spanning tree problem
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: Characterizations of strongly chordal graphs
cites work: Networks immune to isolated failures
cites work: Networks immune to isolated line failures
cites work: Algorithmic graph theory and perfect graphs
cites work: Stability in circular arc graphs
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: Independent Sets in Circular-Arc Graphs
cites work: Linear time algorithms on circular-arc graphs
cites work: An optimal algorithm for finding dominating cycles in circular-arc graphs
cites work: Minimum Cuts for Circular-Arc Graphs
cites work: Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
cites work: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
cites work: Linear-time recognition of circular-arc graphs
cites work: Three Partition Refinement Algorithms
cites work: \(k\) best cuts for circular-arc graphs
cites work: An Efficient Test for Circular-Arc Graphs
DOI: 10.1007/S00453-012-9641-7
description: scientific article; zbMATH DE number 6162398