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]).

efensive alliance, alliances in graphs, treewidth, complexity analysis, parameterized complexity

Electronic version of the publication:

Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.