Paired-domination problem on distance-hereditary graphs
From MaRDI portal
Publication:2006943
DOI10.1007/s00453-020-00705-7zbMath1459.05242OpenAlexW3019251218MaRDI QIDQ2006943
Chan-Hung Hsu, Ching-Chi Lin, Keng-Chu Ku
Publication date: 12 October 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00705-7
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (7)
Complexity of paired domination in AT-free and planar graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Unique response Roman domination: complexity and algorithms ⋮ Complexity of paired domination in at-free and planar graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Domination, independent domination, and duality in strongly chordal graphs
- Dominating sets for split and bipartite graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Completely separable graphs
- 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
- Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Clustering and domination in perfect graphs
- Distance-hereditary graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Labeling algorithms for domination problems in sun-free chordal graphs
- Independent domination in chordal graphs
- Dominating sets in perfect graphs
- Permutation graphs: Connected domination and Steiner trees
- Linear time algorithms on circular-arc graphs
- Topics on domination
- The complexity of domination problems in circle graphs
- A linear algorithm for the domination number of a tree
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Paired-domination in claw-free graphs with minimum degree at least three
- Paired-domination of trees
- An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
- Algorithmic aspects of upper paired-domination in graphs
- Perfectly relating the domination, total domination, and paired domination numbers of a graph
- Capacitated domination: problem complexity and approximation algorithms
- A linear-time algorithm for paired-domination on circular-arc graphs
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
- Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs
- On the Algorithmic Complexity of Total Domination
- Steiner trees, connected domination and strongly chordal graphs
- Domination in permutation graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- Dominating Sets in Chordal Graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Paired-domination in graphs
- Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
- Total domination in interval graphs
- Domination in distance-hereditary graphs
This page was built for publication: Paired-domination problem on distance-hereditary graphs
