Hardness results and approximation algorithm for total liar's domination in graphs
From MaRDI portal
Publication:2015803
DOI10.1007/s10878-012-9542-3zbMath1297.90170OpenAlexW2170298940MaRDI QIDQ2015803
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
graph algorithmapproximation algorithmNP-completenesschordal graphdominationliar's dominationAPX-completeness
Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)
Related Items (5)
Fault tolerant detectors for distinguishing sets in graphs ⋮ Liar's domination in unit disk graphs ⋮ On the total liar's domination of graphs ⋮ Hardness results, approximation and exact algorithms for liar's domination problem in graphs ⋮ Various bounds for liar's domination number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(k\)-tuple total domination in graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- A survey of selected recent results on total domination in graphs
- \(k\)-tuple domination in graphs
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Liar's domination in graphs
- On domination problems for permutation and other graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- Total domination in block graphs
- Double total domination of graphs
- Some APX-completeness results for cubic graphs
- Algorithmic aspect of \(k\)-tuple domination in graphs.
- Liar's domination
- On the Algorithmic Complexity of Total Domination
- Total domination in graphs
- Reducibility among Combinatorial Problems
- Total domination in interval graphs
This page was built for publication: Hardness results and approximation algorithm for total liar's domination in graphs
