{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:06Z","timestamp":1773481866972,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["P30930-N35"],"award-info":[{"award-number":["P30930-N35"]}]},{"name":"Georg Gottlob is a Royal Society Research Professor","award":["201074"],"award-info":[{"award-number":["201074"]}]},{"name":"Royal Society for the present work in the context of the project","award":["201074"],"award-info":[{"award-number":["201074"]}]},{"name":"FWF","award":["W1255-N23"],"award-info":[{"award-number":["W1255-N23"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Structural decomposition methods, such as generalized hypertree decompositions, have been successfully used for solving constraint satisfaction problems (CSPs). As decompositions can be reused to solve CSPs with the same constraint scopes, investing resources in computing good decompositions is beneficial, even though the computation itself is hard. Unfortunately, current methods need to compute a completely new decomposition, even if the scopes change only slightly. In this article, we make the first steps toward solving the problem of updating the decomposition of a CSP\n            <jats:italic>P<\/jats:italic>\n            so that it becomes a valid decomposition of a new CSP\n            <jats:italic>P<\/jats:italic>\n            ' produced by some modification of\n            <jats:italic>P<\/jats:italic>\n            . Even though the problem is hard in theory, we propose and implement a framework for effectively updating generalized hypertree decompositions. The experimental evaluation of our algorithm strongly suggests practical applicability.\n          <\/jats:p>","DOI":"10.1145\/3578266","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T12:09:25Z","timestamp":1672142965000},"page":"1-28","source":"Crossref","is-referenced-by-count":2,"title":["Incremental Updates of Generalized Hypertree Decompositions"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2353-5230","authenticated-orcid":false,"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7601-3727","authenticated-orcid":false,"given":"Matthias","family":"Lanzinger","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4018-4994","authenticated-orcid":false,"given":"Davide Mario","family":"Longo","sequence":"additional","affiliation":[{"name":"TU Wien, Favoritenstra\u00dfe, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7742-0439","authenticated-orcid":false,"given":"Cem","family":"Okulmus","sequence":"additional","affiliation":[{"name":"TU Wien, Favoritenstra\u00dfe, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,3]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"431","volume-title":"Proceedings of the International Conference on Management of Data (SIGMOD\u201916)","author":"Aberger Christopher R.","year":"2016","unstructured":"Christopher R. Aberger, Susan Tu, Kunle Olukotun, and Christopher R\u00e9. 2016. EmptyHeaded: A relational engine for graph processing. In Proceedings of the International Conference on Management of Data (SIGMOD\u201916). 431\u2013446."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-150694"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/239"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90109-W"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-319-98334-9_8","volume-title":"Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP\u201918)","author":"Fichte Johannes Klaus","year":"2018","unstructured":"Johannes Klaus Fichte, Markus Hecher, Neha Lodha, and Stefan Szeider. 2018. An SMT approach to fractional hypertree width. In Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP\u201918). 109\u2013127."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3440015"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/3196959.3196962","volume-title":"Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Fischl Wolfgang","year":"2018","unstructured":"Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler. 2018. General and fractional hypertree decompositions: Hard and easy cases. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 17\u201332."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/76372.77531"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58942-4_1"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3457374"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/161"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412229"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1080\/0952813X.2014.993507"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3301297"},{"key":"e_1_3_3_22_2","unstructured":"CEUR Workshop Proceedings Proceedings of the 16th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA@AI*IA 2009) 589 Mohammed Lalou Zineb Habbas Kamal Amroun Solving hypertree structured CSP: Sequential and parallel approaches 2009"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_3_25_2","first-page":"1","volume-title":"Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX\u201920)","author":"Schidler Andr\u00e9","year":"2020","unstructured":"Andr\u00e9 Schidler and Stefan Szeider. 2020. Computing optimal hypertree decompositions. In Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX\u201920). SIAM, 1\u201311."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/196"},{"key":"e_1_3_3_27_2","first-page":"338","volume-title":"Proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI\u201981)","author":"Seidel Raimund","year":"1981","unstructured":"Raimund Seidel. 1981. A new method for solving constraint satisfaction problems. In Proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI\u201981), Patrick J. Hayes (Ed.). William Kaufmann, 338\u2013342. http:\/\/ijcai.org\/Proceedings\/81-1\/Papers\/062.pdf."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_3_29_2","first-page":"82","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases. 82\u201394."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578266","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3578266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:21Z","timestamp":1750182561000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":28,"alternative-id":["10.1145\/3578266"],"URL":"https:\/\/doi.org\/10.1145\/3578266","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,31]]}}}