Talks and Poster Presentations (with Proceedings-Entry):
A. Schidler, S. Szeider:
"Computing Optimal Hypertree Decompositions with SAT";
Talk: IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence,
Montreal, Canada;
2021-08-19
- 2021-08-27; in: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)",
(2021),
ISBN: 978-0-9992411-9-6;
1418
- 1424.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.24963/ijcai.2021/196
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_300141.pdf
Created from the Publication Database of the Vienna University of Technology.