<div class="csl-bib-body">
<div class="csl-entry">Bliem, B., & Woltran, S. (2018). Defensive alliances in graphs of bounded treewidth. <i>Discrete Applied Mathematics</i>, <i>251</i>, 334–339. https://doi.org/10.1016/j.dam.2018.04.001</div>
</div>
-
dc.identifier.issn
0166-218X
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/145574
-
dc.description.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]).
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartof
Discrete Applied Mathematics
-
dc.subject
Applied Mathematics
en
dc.subject
Discrete Mathematics and Combinatorics
en
dc.subject
parameterized complexity
en
dc.subject
complexity analysis
en
dc.subject
treewidth
en
dc.subject
alliances in graphs
en
dc.subject
efensive alliance
en
dc.title
Defensive alliances in graphs of bounded treewidth
en
dc.type
Artikel
de
dc.type
Article
en
dc.description.startpage
334
-
dc.description.endpage
339
-
dc.relation.grantno
P25607-N23
-
dc.relation.grantno
Y 698-N23
-
dc.type.category
Original Research Article
-
tuw.container.volume
251
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
tuw.project.title
Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving
-
tuw.project.title
START
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
dcterms.isPartOf.title
Discrete Applied Mathematics
-
tuw.publication.orgunit
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
tuw.publisher.doi
10.1016/j.dam.2018.04.001
-
dc.date.onlinefirst
2018-11-28
-
dc.identifier.eissn
1872-6771
-
dc.description.numberOfPages
6
-
tuw.author.orcid
0000-0002-2898-2830
-
tuw.author.orcid
0000-0003-1594-8972
-
wb.sci
true
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.facultyfocus
Logic and Computation (LC)
de
wb.facultyfocus
Logic and Computation (LC)
en
wb.facultyfocus.faculty
E180
-
item.fulltext
no Fulltext
-
item.openairetype
research article
-
item.languageiso639-1
en
-
item.grantfulltext
restricted
-
item.openairecristype
http://purl.org/coar/resource_type/c_2df8fbb1
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E184 - Institut für Informationssysteme
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.orcid
0000-0003-1594-8972
-
crisitem.author.parentorg
E180 - Fakultät für Informatik
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
