<div class="csl-bib-body">
<div class="csl-entry">Eiben, E. (2018). <i>Exploiting new types of structure for fixed-parameter tractability</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.55516</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2018.55516
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/3524
-
dc.description.abstract
The design of efficient algorithms for various problems is a fundamental part of computer science. One significant obstacle in this area is the fact that many interesting problems from areas such as Algorithmic Graph Theory, Artificial Intelligence, or Optimization are known to be NP-hard on general instances. However, in the majority of applications the instances of interest are the result or output of some other processes, and as such inherently contain some form of structure. This structure can often be exploited to efficiently find exact solutions for many NP-hard problems. To capture the structure of the input instance, we use the framework of parameterized complexity. In parameterized algorithms, the running time is analyzed in finer detail than in classical complexity theory: instead of expressing the running time as a function of the input size only, dependence on a parameter k is taken into account. We use the parameter k to describe how “structured” the input instance is. Algorithms with running time f(k)nc, where n is the input size and c is a constant independent of both n and k, are called fixed-parameter algorithms or FPT algorithms. Typically the goal in parameterized algorithms is to design FPT algorithms while minimizing both the f(k) factor and the constant c in the bound on the running time. We study a range of different problems under the paradigm of parameterized complexity. More precisely, our research focuses on two approaches to analyze the structure of instances and their combination. The first approach focuses on the notion of decomposition. The idea is to decompose the given input into simpler parts and use this decomposition to solve the problem more efficiently. The second approach is based on the established notion of a modulator to a tractable class of instances, which applies to problem instances that may be placed in a tractable class by a small number of local changes. We design several algorithms that exploit some of the already established parameters. However, our main focus is on designing and exploiting new kinds of structure. We highlight here one of the results in particular. We develop a family of parameters that combine the two approaches outlined above to capture forms of structure not accessible to a single approach, and we show that these parameters give rise to efficient algorithms for a plethora of NP-hard problems.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
parameterized complexity
en
dc.subject
fixed-parameter algorithms
en
dc.subject
FPT
en
dc.subject
structural parameters
en
dc.subject
decomposition
en
dc.subject
modulator
en
dc.title
Exploiting new types of structure for fixed-parameter tractability
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2018.55516
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Eduard Eiben
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Gottlob, Georg
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC15020516
-
dc.description.numberOfPages
272
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-112028
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
tuw.author.orcid
0000-0003-2628-3435
-
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
staff
-
tuw.advisor.orcid
0000-0001-8994-1656
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
item.openairetype
doctoral thesis
-
item.grantfulltext
open
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen