Labelling algorithms for paired-domination problems in block and interval graphs
From MaRDI portal
Publication:987497
DOI10.1007/s10878-008-9177-6zbMath1197.90336arXiv0802.2742OpenAlexW2113061047WikidataQ60630607 ScholiaQ60630607MaRDI QIDQ987497
Lei Chen, Zhenbing Zeng, Chang-hong Lu
Publication date: 13 August 2010
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0802.2742
Related Items (32)
Semipaired Domination in Some Subclasses of Chordal Graphs ⋮ Computing a minimum paired-dominating set in strongly orderable graphs ⋮ Upper bounds for the paired-domination numbers of graphs ⋮ Paired-domination in claw-free graphs ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Vertices in all minimum paired-dominating sets of block graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Algorithmic aspects of paired disjunctive domination in graphs ⋮ Complexity of paired domination in at-free and planar graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ On computing a minimum secure dominating set in block graphs ⋮ A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph ⋮ 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 ⋮ Complexity of distance paired-domination problem in graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ An efficient algorithm for distance total domination in block graphs ⋮ \(k\)-power domination in block 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 ⋮ Hardness results and approximation algorithms for (weighted) paired-domination in graphs ⋮ Distance paired-domination problems on subclasses of chordal graphs ⋮ Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs ⋮ A linear-time algorithm for paired-domination on circular-arc graphs ⋮ Roman \(\{2\}\)-domination problem in graphs
Cites Work
- Graphs with large paired-domination number
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Paired-domination of trees
- Paired domination on interval and circular-arc graphs
- Paired-domination in generalized claw-free graphs
- Paired-domination in graphs
This page was built for publication: Labelling algorithms for paired-domination problems in block and interval graphs