Beiträge in Tagungsbänden:
R. Ganian, M. S. Ramanujan, S. Szeider:
"Combining Treewidth and Backdoors for CSP";
in: "34th Symposium on Theoretical Aspects of Computer Science",
herausgegeben von: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik;
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany,
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik,
2017,
ISBN: 978-3-95977-028-6,
S. 429
- 445.
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 parti- tions and
elimination orderings. We empirically obtained SAT-encodings.
Schlagworte:
Algorithms and data structures, Fixed Parameter Tractability, Constraint Satisfaction
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.STACS.2017.36
Elektronische Version der Publikation:
http://drops.dagstuhl.de/opus/volltexte/2017/6998/
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.