A linear-time algorithm for paired-domination on circular-arc graphs

DOI10.1016/J.TCS.2015.05.002zbMath1322.05130OpenAlexW314002464MaRDI QIDQ2354407

Ching-Chi Lin, Hai-Lun Tu

Publication date: 13 July 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.05.002

zbMATH Keywords

interval graphperfect matchingcircular-arc graphpaired-domination problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

Complexity of paired domination in AT-free and planar graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Complexity of paired domination in at-free and planar graphs ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Paired Domination in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Paired-domination in inflated graphs
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Locating and paired-dominating sets in graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• A survey of selected recent results on total domination in graphs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• Topics on domination
• Linear-time recognition of circular-arc graphs
• Paired-domination of trees
• Power domination in circular-arc graphs
• Independent domination in graphs: A survey and recent results
• Paired domination on interval and circular-arc graphs
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Paired-domination in graphs
• Hamilton cycles in split graphs with large minimum degree

This page was built for publication: A linear-time algorithm for paired-domination on circular-arc graphs