[Back]


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.