<div class="csl-bib-body">
<div class="csl-entry">Parlak, A. (2016). <i>A SAT spproach to clique-width of a digraph and an application on model counting problems</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.39609</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2016.39609
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/6865
-
dc.description
Zusammenfassung in deutscher Sprache
-
dc.description
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
-
dc.description.abstract
Introduced by Courcelle, Engelfriet, and Rozenberg, clique-width is a fundamental graph invariant that has been widely studied in discrete mathematics and computer science. Many hard problems on graphs and digraphs become tractable when restricted to graphs and digraphs of small clique-width, indeed solvable in linear time when restricted to classes of bounded clique-width. Clique-width is more general than treewidth, in the sense that algorithms parameterized by clique-width are effective on larger classes of instances than algorithms parameterized by treewidth (as there are graph classes of bounded clique-width where treewidth is unbounded, whereas small treewidth implies small clique-width). Typically algorithms for graphs of small clique-width require as input a certificate for small clique-width, which is already computationally hard to compute. In recent work Heule and Szeider presented a method for computing the clique-width of graphs based on an encoding to propositional satisfiability (SAT), which is then evaluated by a SAT solver, managing to discover the exact clique-width of various small graphs, previously unknown. Our main contribution is a generalization of the method by Heule and Szeider to directed graphs. Namely we present and implement an algorithm that, by invoking a SAT solver on a suitable instance, certifies the clique-width of a given directed graph. We exploit this implementation in two ways. First, we find the exact clique-width of various small directed graphs. Second, we implement an algorithm by Fischer, Makowsky, and Ravve and combine this and the aforementioned to an algorithm that counts models of CNFformulas of small directed incidence clique-width.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Cliquenweite
de
dc.subject
SAT-Kodierung
de
dc.subject
Zählen von Modellen
de
dc.subject
Clique-width
en
dc.subject
SAT Encoding
en
dc.subject
Model Counting
en
dc.title
A SAT spproach to clique-width of a digraph and an application on model counting problems
en
dc.title.alternative
Ein SAT-Ansatz zur Cliquenweite von Digraphen und eine Anwendung auf das Zählen von Modellen
de
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.2016.39609
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Aykut Parlak
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Bova, Simone Maria
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen