Beiträge in Tagungsbänden:
T. Peitl, F. Slivovsky, S. Szeider:
"Dependency Learning for QBF";
in: "Theory and Applications of Satisfiability Testing - SAT 2017",
© Springer International Publishing AG 2017,
2017,
ISBN: 978-3-319-66263-3,
S. 198
- 313.
Kurzfassung englisch:
Decomposition width parameters such as treewidth provide a measurement on the complexity of a graph. Finding a decomposition of smallest width is itself NP-hard but lends itself to a SAT-based solution. Previous work on treewidth, branchwidth and clique-width indicates that identifying a suitable characterization of the considered decomposition method is key for a practically feasible SAT-encoding.
In this paper we study SAT-encodings for the decomposition width parameters special treewidth and pathwidth. In both cases we develop SAT-encodings based on two different characterizations. In particular, we develop two novel characterizations for special treewidth based on partitions and elimination orderings. We empirically obtained SAT-encodings.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-66263-3_27
Elektronische Version der Publikation:
https://link.springer.com/chapter/10.1007%2F978-3-319-66263-3_27
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.