Paired domination on interval and circular-arc graphs
From MaRDI portal
Publication:2384392
DOI10.1016/j.dam.2007.05.011zbMath1124.05070MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Which trees have a differentiating-paired dominating set?, Graphs with disjoint dominating and paired-dominating sets, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, An upper bound on the paired-domination number in terms of the number of edges in the graph, Well paired-dominated graphs, A characterization of graphs with disjoint dominating and paired-dominating sets, Upper paired-domination in claw-free graphs, A characterization of cubic graphs with paired-domination number three-fifths their order, Labelling algorithms for paired-domination problems in block and interval graphs, A linear-time algorithm for paired-domination problem in strongly chordal graphs, A polynomial-time algorithm for the paired-domination problem on 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, Complexity of distance paired-domination problem in graphs, Linear-time algorithm for the matched-domination problem in cographs
Cites Work
- Unnamed Item
- 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
