Complexity of distance paired-domination problem in graphs

DOI10.1016/J.TCS.2012.08.024MaRDI QIDQ1758170zbMATH OpenOpenAlexFDO

Authors 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 algorithmAPX-completedistance \(k\)-dominating setdistance \(k\)-paired-dominating setNP-completestrongly chordal graphundirected path graph

Mathematics Subject Classification ID

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

Recommendations

• Distance paired-domination problems on subclasses of chordal graphs
• Paired-domination problem on distance-hereditary graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs

Cites work

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

Cited in

(9)

• Distance paired-domination problems on subclasses of chordal graphs
• Computing a minimum paired-dominating set in strongly orderable graphs
• On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs
• Algorithmic aspects of upper paired-domination in graphs
• An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
• Parameterized and approximation complexity of the detection pair problem in graphs
• The complexity of obtaining a distance-balanced graph
• Complexity results on paired domination in cubic graphs
• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1758170)