Approximation algorithm and hardness results for defensive domination in graphs

DOI10.1007/978-3-030-92681-6_21OpenAlexW4206047854MaRDI QIDQ2149875

Arti Pandey, Vikash Tripathi, Michael A. Henning

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_21

zbMATH Keywords

NP-completenessgraph algorithmsdominationapproximation algorithmsAPX-completenessdefensive domination

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation hardness of dominating set problems in bounded degree graphs
• Some APX-completeness results for cubic graphs
• On the approximability and exact algorithms for vector domination and related problems in graphs
• The complexity of the defensive domination problem in special graph classes
• Cops, a fast robber and defensive domination on interval graphs
• Alliances and Related Domination Parameters
• Algorithms and Complexity of Alliances in Graphs
• Structures of Domination in Graphs
• Topics in Domination in Graphs
• Analytical approach to parallel repetition

This page was built for publication: Approximation algorithm and hardness results for defensive domination in graphs