Zeitschriftenartikel:
B. Bliem, S. Woltran:
"Defensive alliances in graphs of bounded treewidth";
Discrete Applied Mathematics,
251
(2018),
251;
S. 334
- 339.
Kurzfassung englisch:
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]).
Schlagworte:
efensive alliance, alliances in graphs, treewidth, complexity analysis, parameterized complexity
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_273979.pdf
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.