Complexity of distance paired-domination problem in graphs

DOI10.1016/j.tcs.2012.08.024zbMath1250.68119OpenAlexW2092122769MaRDI QIDQ1758170

Xianqiang Yang

Publication date: 8 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.08.024

zbMATH Keywords

approximation algorithmNP-completeAPX-completestrongly chordal graphundirected path graphdistance \(k\)-dominating setdistance \(k\)-paired-dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (3)

Computing a minimum paired-dominating set in strongly orderable graphs ⋮ \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms] ⋮ Algorithmic aspects of upper paired-domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path 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
• \(k\)-tuple domination in graphs
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• Distance paired-domination problems on subclasses of chordal graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• Optimization, approximation, and complexity classes
• A recognition algorithm for the intersection graphs of paths in trees
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Paired-domination of trees
• A characterisation of rigid circuit graphs
• Doubly lexical ordering of dense 0--1 matrices
• Paired domination on interval and circular-arc graphs
• Incidence matrices and interval graphs
• Distance paired domination numbers of graphs
• Characterizations of trees with equal paired and double domination numbers
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A threshold of ln n for approximating set cover
• Characterizations of totally balanced matrices
• Totally-Balanced and Greedy Matrices
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Steiner trees, connected domination and strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• Representations of chordal graphs as subtrees of a tree
• Paired-domination in graphs

This page was built for publication: Complexity of distance paired-domination problem in graphs