Liar's domination in graphs: complexity and algorithm

DOI10.1016/j.dam.2012.12.011zbMath1263.05074OpenAlexW2052665499MaRDI QIDQ1949115

B. S. Panda, Subhabrata Paul

Publication date: 25 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.12.011

zbMATH Keywords

graph algorithmNP-completenessdominationLiar's domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

Liar's dominating sets in graphs ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Liar's dominating set problem on unit disk graphs ⋮ Liar’s Domination in 2D ⋮ Liar's domination in unit disk graphs ⋮ Hardness results, approximation and exact algorithms for liar's domination problem in graphs ⋮ Various bounds for liar's domination number ⋮ Bounds on co-independent liar's domination in graphs ⋮ On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Liar's domination in graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• A linear algorithm for the domination number of a tree
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Liar's domination
• On the Algorithmic Complexity of Total Domination
• The edge domination problem
• Reducibility among Combinatorial Problems

This page was built for publication: Liar's domination in graphs: complexity and algorithm