On structural parameterizations of the offensive alliance problem

DOI10.1007/978-3-030-92681-6_45OpenAlexW3210850331MaRDI QIDQ2150581

Soumen Maity, Ajinkya Gaikwad

Publication date: 29 June 2022

Full work available at URL: https://arxiv.org/abs/2110.15757

zbMATH Keywords

treewidthparameterized complexityFPTW[1-hard]defensive and offensive alliance

Mathematics Subject Classification ID

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

Related Items

Defensive alliances in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• On the global offensive alliance number of a graph
• On the complement graph and defensive \(k\)-alliances
• Treewidth. Computations and approximations
• Defensive alliances in graphs of bounded treewidth
• Alliances in graphs of bounded clique-width
• On structural parameterizations of the bounded-degree vertex deletion problem
• On defensive alliances and line graphs
• Global offensive alliances in graphs
• Kernelization
• Global alliances and independence in trees
• Parameterized Algorithms