Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
A. Schidler, S. Szeider:
"Computing Optimal Hypertree Decompositions with SAT";
Vortrag: IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence,
Montreal, Canada;
19.08.2021
- 27.08.2021; in: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)",
(2021),
ISBN: 978-0-9992411-9-6;
S. 1418
- 1424.
Kurzfassung englisch:
Hypertree width is a prominent hypergraph invariant
with many algorithmic applications in constraint
satisfaction and databases. We propose a novel characterization
for hypertree width in terms of linear
elimination orderings. We utilize this characterization
to generate a new SAT encoding that we evaluate
on an extensive set of benchmark instances. We
compare it to state-of-the-art exact methods for computing
optimal hypertree width. Our results show
that the encoding based on the new characterization
is not only significantly more compact than known
encodings but also outperforms the other methods.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/ijcai.2021/196
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_300141.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.