Format:
1 Online-Ressource (xv, 184 Seiten, 5392 KB)
,
Illustrationen, Diagramme
Content:
In the last decades, there was a notable progress in solving the well-known Boolean satisfiability (Sat) problem, which can be witnessed by powerful Sat solvers. One of the reasons why these solvers are so fast are structural properties of instances that are utilized by the solver’s interna. This thesis deals with the well-studied structural property treewidth, which measures the closeness of an instance to being a tree. In fact, there are many problems parameterized by treewidth that are solvable in polynomial time in the instance size when parameterized by treewidth. In this work, we study advanced treewidth-based methods and tools for problems in knowledge representation and reasoning (KR). Thereby, we provide means to establish precise runtime results (upper bounds) for canonical problems relevant to KR. Then, we present a new type of problem reduction, which we call decomposition-guided (DG) that allows us to precisely monitor the treewidth when reducing from one problem to another problem. This new reduction type will be the ...
Note:
Dissertation Technische Universität Wien 2021
,
Dissertation Universität Potsdam 2021
Additional Edition:
Erscheint auch als Druck-Ausgabe Hecher, Markus Advanced tools and methods for treewidth-based problem solving Potsdam, 2021
Language:
English
Keywords:
Hochschulschrift
DOI:
10.25932/publishup-51251
URN:
urn:nbn:de:kobv:517-opus4-512519
URL:
https://doi.org/10.25932/publishup-51251
URL:
https://nbn-resolving.org/urn:nbn:de:kobv:517-opus4-512519
URL:
https://d-nb.info/1238686745/34
Author information:
Vollmer, Heribert 1964-
Bookmarklink