[Zurück]

N. Lodha, S. Ordyniak, S. Szeider:
"SAT-Encodings for Special Treewidth and Pathwidth";
in: "Theory and Applications of Satisfiability Testing - SAT 2017", Springer International Publishing AG 2017, 2017, ISBN: 978-3-319-66263-3, S. 429 - 445.

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.

http://dx.doi.org/10.1007/978-3-319-66263-3_27

https://link.springer.com/chapter/10.1007%2F978-3-319-66263-3_27