Paired-domination problem on distance-hereditary graphs
type: Item
instance of: scholarly article
title: Paired-domination problem on distance-hereditary graphs
zbMATH Open document ID: 1459.05242
author: Ching-Chi Lin
author: Keng-Chu Ku
author: Chan-Hung Hsu
published in: Algorithmica
publication date: 2020-10-12T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7259195
zbMATH Keywords: paired-domination
zbMATH Keywords: perfect matching
zbMATH Keywords: distance-hereditary graphs
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
full work available at URL: s00453-020-00705-7
OpenAlex ID: W3019251218
cites work: Perfectly relating the domination, total domination, and paired domination numbers of a graph
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Q4258216
cites work: Distance-hereditary graphs
cites work: Dominating sets for split and bipartite graphs
cites work: Q3206969
cites work: Dominating Sets in Chordal Graphs
cites work: Q3694712
cites work: Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs
cites work: Labeling algorithms for domination problems in sun-free chordal graphs
cites work: Q4247463
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: Domination in distance-hereditary graphs
cites work: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
cites work: Hardness results and approximation algorithms for (weighted) paired-domination in graphs
cites work: A linear-time algorithm for paired-domination problem in strongly chordal graphs
cites work: Labelling algorithms for paired-domination problems in block and interval graphs
cites work: A polynomial-time algorithm for the paired-domination problem on permutation graphs
cites work: A linear algorithm for the domination number of a tree
cites work: Permutation graphs: Connected domination and Steiner trees
cites work: Clustering and domination in perfect graphs
cites work: Dominating sets in perfect graphs
cites work: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
cites work: Paired domination in graphs: a survey and recent results
cites work: Independent domination in chordal graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Domination in permutation graphs
cites work: Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
cites work: Q4198056
cites work: New geometric representations and domination problems on tolerance and multitolerance graphs
cites work: Completely separable graphs
cites work: Q4368729
cites work: Q4368728
cites work: Paired-domination in graphs
cites work: Bibliography on domination in graphs and some basic definitions of domination parameters
cites work: Topics on domination
cites work: Algorithmic aspects of upper paired-domination in graphs
cites work: Q3002852
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs
cites work: Linear time algorithms on circular-arc graphs
cites work: Capacitated domination: problem complexity and approximation algorithms
cites work: Total domination in interval graphs
cites work: The complexity of domination problems in circle graphs
cites work: An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
cites work: On the Algorithmic Complexity of Total Domination
cites work: A linear-time algorithm for paired-domination on circular-arc graphs
cites work: Paired-domination in claw-free graphs with minimum degree at least three
cites work: Paired-domination of trees
cites work: Steiner trees, connected domination and strongly chordal graphs
cites work: Weighted connected domination and Steiner trees in distance-hereditary graphs
DOI: 10.1007/S00453-020-00705-7
description: scientific article; zbMATH DE number 7259195