Paired domination on interval and circular-arc graphs
From MaRDI portal
Publication:2384392
DOI10.1016/j.dam.2007.05.011zbMath1124.05070OpenAlexW1995629519MaRDI QIDQ2384392
Publication date: 21 September 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10397/478
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (31)
Paired-domination in claw-free graphs ⋮ Graphs with disjoint dominating and paired-dominating sets ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Total domination versus paired-domination in regular graphs ⋮ A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph ⋮ Graphs with maximum size and given paired-domination number ⋮ Paired-domination in claw-free graphs with minimum degree at least three ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ On the distance paired domination of generalized Petersen graphs \(P(n,1)\) and \(P(n,2)\) ⋮ Complexity of distance paired-domination problem in graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ A characterization of cubic graphs with paired-domination number three-fifths their order ⋮ Which trees have a differentiating-paired dominating set? ⋮ Paired-domination number of claw-free odd-regular graphs ⋮ An upper bound on the paired-domination number in terms of the number of edges in the graph ⋮ Well paired-dominated graphs ⋮ Labelling algorithms for paired-domination problems in block and interval graphs ⋮ A characterization of graphs with disjoint dominating and paired-dominating sets ⋮ Upper paired-domination in claw-free graphs ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ Paired Domination in Graphs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Constructive characterizations of \( (\gamma_p,\gamma)\)-and \( (\gamma_p, \gamma_{pr})\)-trees ⋮ Hardness results and approximation algorithms for (weighted) paired-domination in graphs ⋮ Distance paired-domination problems on subclasses of chordal graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ My Favorite Domination Conjectures in Graph Theory Are Bounded ⋮ A linear-time algorithm for paired-domination on circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Interval graphs and related topics
- Dominating sets and domatic number of circular arc graphs
- Total domination in interval graphs revisited
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Paired-domination of trees
- On the Algorithmic Complexity of Total Domination
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Paired-domination in graphs
This page was built for publication: Paired domination on interval and circular-arc graphs
