[Zurück]


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.