Liar's domination in graphs: complexity and algorithm

DOI10.1016/J.DAM.2012.12.011MaRDI QIDQ1949115zbMATH OpenOpenAlexFDO

Authors B. S. Panda, S. 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

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

Recommendations

• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Connected liar's domination in graphs: complexity and algorithms
• Hardness results and approximation algorithm for total liar's domination in graphs
• A linear time algorithm for liar's domination problem in proper interval graphs
• scientific article; zbMATH DE number 6470870

Cites work

• scientific article; zbMATH DE number 5533277 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• A linear algorithm for the domination number of a tree
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Labeling algorithms for domination problems in sun-free chordal graphs
• Liar's domination
• Liar's domination in graphs
• On the Algorithmic Complexity of Total Domination
• Reducibility among combinatorial problems
• The edge domination problem

Cited in

(17)

• On the total liar's domination of graphs
• On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs
• Liar's domination in graphs under some operations
• Bounds on co-independent liar's domination in graphs
• Hardness results and approximation algorithm for total liar's domination in graphs
• Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
• Algorithmic study on liar's vertex-edge domination problem
• Connected liar's domination in graphs: complexity and algorithms
• Liar's domination in Sierpinski-like graphs
• Various bounds for liar's domination number
• Liar's dominating set problem on unit disk graphs
• Liar's domination in unit disk graphs
• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Liar's dominating sets in graphs
• scientific article; zbMATH DE number 7350751 (Why is no real title available?)
• A linear time algorithm for liar's domination problem in proper interval graphs
• Liar's domination in 2D

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

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