Hardness results and approximation algorithm for total liar's domination in graphs

DOI10.1007/S10878-012-9542-3zbMATH Open1297.90170OpenAlexW2170298940MaRDI QIDQ2015803FDOQ2015803

Authors B. S. Panda, S. Paul 

Publication date 24 June 2014

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-012-9542-3

zbMATH Keywords

approximation algorithmgraph algorithmNP-completenessdominationchordal graphliar's dominationAPX-completeness

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Liar's domination in graphs: complexity and algorithm
• Connected liar's domination in graphs: complexity and algorithms
• A linear time algorithm for liar's domination problem in proper interval graphs
• Liar's dominating sets in graphs

Cites work

• scientific article; zbMATH DE number 5533277 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (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?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• A survey of selected recent results on total domination in graphs
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Approximation hardness of dominating set problems in bounded degree graphs
• Double total domination of graphs
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Introduction to algorithms
• Labeling algorithms for domination problems in sun-free chordal graphs
• Liar's domination
• Liar's domination in graphs
• On domination problems for permutation and other graphs
• On the Algorithmic Complexity of Total Domination
• Reducibility among combinatorial problems
• Some APX-completeness results for cubic graphs
• Total domination in block graphs
• Total domination in graphs
• Total domination in interval graphs
• \(k\)-tuple domination in graphs
• \(k\)-tuple total domination in graphs

Cited in

(9)

• On the total liar's domination of graphs
• Fault tolerant detectors for distinguishing sets in graphs
• Algorithmic study on liar's vertex-edge domination problem
• Liar's domination in graphs: complexity and algorithm
• Connected liar's domination in graphs: complexity and algorithms
• Various bounds for liar's domination number
• Liar's domination in unit disk graphs
• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• A linear time algorithm for liar's domination problem in proper interval graphs

This page was built for publication: Hardness results and approximation algorithm for total liar's domination in graphs

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