A linear-time algorithm for paired-domination on circular-arc graphs
From MaRDI portal
Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- Paired domination on interval and circular-arc graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
Cites work
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- A survey of selected recent results on total domination in graphs
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Hamilton cycles in split graphs with large minimum degree
- Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- scientific article; zbMATH DE number 1302196 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- Independent domination in graphs: A survey and recent results
- Labelling algorithms for paired-domination problems in block and interval graphs
- Linear-time algorithm for the paired-domination problem in convex bipartite graphs
- Linear-time recognition of circular-arc graphs
- Locating and paired-dominating sets in graphs
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- Paired domination on interval and circular-arc graphs
- Paired-domination in graphs
- Paired-domination in inflated graphs
- Paired-domination of trees
- Power domination in circular-arc graphs
- Topics on domination
Cited in
(16)- An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
- Paired-domination problem on distance-hereditary graphs
- Complexity of paired domination in AT-free and planar graphs
- A linear-time algorithm for weighted paired-domination on block graphs
- Paired domination on interval and circular-arc graphs
- Linear-time algorithm for the matched-domination problem in cographs
- Paired domination in graphs
- Hamilton cycles in split graphs with large minimum degree
- Complexity of paired domination in at-free and planar graphs
- Linear-time algorithm for paired-domination on distance-hereditary graphs
- Leaf sector covers with applications on circle graphs
- Linear-time algorithm for the paired-domination problem in convex bipartite graphs
- Complexity results on paired domination in cubic graphs
- A constant factor approximation algorithm for boxicity of circular arc graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
This page was built for publication: A linear-time algorithm for paired-domination on circular-arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354407)
