CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS

DOI10.1142/S1793830913500249zbMath1280.05103OpenAlexW2083328367MaRDI QIDQ2874035

B. S. Panda, Subhabrata Paul

Publication date: 28 January 2014

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830913500249

zbMATH Keywords

graph algorithmapproximation algorithmNP-completenesschordal graphdominationliar's dominationAPX-completeness

Mathematics Subject Classification ID

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 (2)

Liar's domination in unit disk graphs ⋮ Hardness results, approximation and exact algorithms for liar's domination problem in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation hardness of dominating set problems in bounded degree graphs
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Liar's domination in graphs
• Permutation graphs: Connected domination and Steiner trees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Liar's domination
• Paired-domination in graphs

This page was built for publication: CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS