Talks and Poster Presentations (with Proceedings-Entry):
A. Schidler, S. Szeider:
"Computing Optimal Hypertree Decompositions";
Talk: Workshop on Algorithm Engineering and Experiments (ALENEX),
Salt Lake City, USA;
2020-01-05
- 2020-01-06; in: "Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)",
siam,
(2020),
ISBN: 978-1-61197-600-7;
1
- 11.
English abstract:
We propose a new algorithmic method for computing the hypertreewidth of hypergraphs, and we evaluate its performance empirically.At the core of our approach lies a novel ordering based character-ization of hypertree width which lends to an efficient encoding toSAT modulo Theory (SMT). We tested our algorithm on an exten-sive benchmark set consisting of real-world instances from varioussources. Our approach outperforms state-of-the-art algorithms forhypertree width. We achieve a further speedup by a new techniquethat first solves a relaxation of the problem and subsequently usesthe solution to guide the algorithm for solving the problem itself
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1137/1.9781611976007.1
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_292337.pdf
Created from the Publication Database of the Vienna University of Technology.