{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T04:39:19Z","timestamp":1723264759039},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>Hypertree width is a prominent hypergraph invariant with many\n\n  algorithmic applications in constraint satisfaction and\n\n  databases. We propose a novel characterization for hypertree width\n\n  in terms of linear elimination orderings. We utilize this\n\n  characterization to generate a new SAT encoding that we evaluate on\n\n  an extensive set of benchmark instances. We compare it to\n\n  state-of-the-art exact methods for computing optimal hypertree\n\n  width. Our results show that the encoding based on the new\n\n  characterization is not only significantly more compact than known\n\n  encodings but also outperforms the other methods.<\/jats:p>","DOI":"10.24963\/ijcai.2021\/196","type":"proceedings-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:00:49Z","timestamp":1628679649000},"page":"1418-1424","source":"Crossref","is-referenced-by-count":3,"title":["Computing Optimal Hypertree Decompositions with SAT"],"prefix":"10.24963","author":[{"given":"Andre","family":"Schidler","sequence":"first","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Vienna, Austria"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, TU Wien, Vienna, Austria"}]}],"member":"10584","event":{"number":"30","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2021","name":"Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}","start":{"date-parts":[[2021,8,19]]},"theme":"Artificial Intelligence","location":"Montreal, Canada","end":{"date-parts":[[2021,8,27]]}},"container-title":["Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:01:55Z","timestamp":1628679715000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2021\/196"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2021,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2021\/196","relation":{},"subject":[],"published":{"date-parts":[[2021,8]]}}}