Publications in Scientific Journals:
B. Bliem, S. Woltran:
"Defensive alliances in graphs of bounded treewidth";
Discrete Applied Mathematics,
251
(2018),
251;
334
- 339.
English abstract:
The Defensive Alliance problem has been studied extensively during the last fifteen years, but the question whether it is FPT when parameterized by treewidth has still remained open. We show that this problem is W[1]-hard. This puts it among the few problems that are FPT when parameterized by solution size but not when parameterized by treewidth (unless FPT = W[1]).
Keywords:
efensive alliance, alliances in graphs, treewidth, complexity analysis, parameterized complexity
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_273979.pdf
Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen
Project Head Stefan Woltran:
START
Created from the Publication Database of the Vienna University of Technology.