{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:30Z","timestamp":1750309110373,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P17222-N04"],"award-info":[{"award-number":["P17222-N04"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"<jats:p>\n            Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the acyclicity and therefore an indicator for the tractability of the associated computation problem. Several NP-hard decision and computation problems are known to be tractable on instances whose structure is represented by hypergraphs of bounded hypertree-width. Roughly speaking, the smaller the hypertree-width, the faster the computation problem can be solved. In this paper, we present the new backtracking-based algorithm det-\n            <jats:italic>k<\/jats:italic>\n            -decomp for computing hypertree decompositions of small width. Our benchmark evaluations have shown that det-\n            <jats:italic>k<\/jats:italic>\n            -decomp significantly outperforms opt-\n            <jats:italic>k<\/jats:italic>\n            -decomp, the only exact hypertree decomposition algorithm so far. Even compared to the best heuristic algorithm, we obtained competitive results as long as the hypergraphs are sufficiently simple.\n          <\/jats:p>","DOI":"10.1145\/1412228.1412229","type":"journal-article","created":{"date-parts":[[2008,10,7]],"date-time":"2008-10-07T12:48:29Z","timestamp":1223383709000},"source":"Crossref","is-referenced-by-count":18,"title":["A backtracking-based algorithm for hypertree decomposition"],"prefix":"10.1145","volume":"13","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, England, UK"}]},{"given":"Marko","family":"Samer","sequence":"additional","affiliation":[{"name":"University of Durham, Durham, England, UK"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30577-4_1"},{"volume-title":"Chapt. 4, Morgan Kaufmann","author":"Dechter R.","key":"e_1_2_1_2_1","unstructured":"Dechter , R. 2003. Constraint Processing , Chapt. 4, Morgan Kaufmann , Burlington, MA . 85--115. Dechter, R. 2003. Constraint Processing, Chapt. 4, Morgan Kaufmann, Burlington, MA. 85--115."},{"key":"e_1_2_1_3_1","unstructured":"Ganzow T. Gottlob G. Musliu N. and Samer M. 2005. A CSP hypergraph library. Tech. Rept. DBAI-TR-2005-50 Institute of Information Systems (DBAI) TU Vienna.  Ganzow T. Gottlob G. Musliu N. and Samer M. 2005. A CSP hypergraph library. Tech. Rept. DBAI-TR-2005-50 Institute of Information Systems (DBAI) TU Vienna."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of 10th International Conference on Database and Expert System Applications (DEXA). Lecture Notes in Computer Science","volume":"1677","author":"Gottlob G.","unstructured":"Gottlob , G. , Leone , N. , and Scarcello , F . 1999. On tractable queries and constraints . In Proceedings of 10th International Conference on Database and Expert System Applications (DEXA). Lecture Notes in Computer Science , vol. 1677 . Springer-Verlag, New York. 1--15. Gottlob, G., Leone, N., and Scarcello, F. 1999. On tractable queries and constraints. In Proceedings of 10th International Conference on Database and Expert System Applications (DEXA). Lecture Notes in Computer Science, vol. 1677. Springer-Verlag, New York. 1--15."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00030-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265533"},{"volume-title":"Proceedings of 15th International Conference on Tools with Artificial Intelligence (ICTAI'03)","author":"Harvey P.","key":"e_1_2_1_8_1","unstructured":"Harvey , P. and Ghose , A . 2003. Reducing redundancy in the hypertree decomposition scheme . In Proceedings of 15th International Conference on Tools with Artificial Intelligence (ICTAI'03) . IEEE Computer Society, Los Alamitos, CA. 474--481. Harvey, P. and Ghose, A. 2003. Reducing redundancy in the hypertree decomposition scheme. In Proceedings of 15th International Conference on Tools with Artificial Intelligence (ICTAI'03). IEEE Computer Society, Los Alamitos, CA. 474--481."},{"key":"e_1_2_1_10_1","volume-title":"Treewidth: Computational experiments. Tech. Rept. ZIB-Report 01-38, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin (ZIB).","author":"Koster A. M. C. A.","year":"2001","unstructured":"Koster , A. M. C. A. , Bodlaender , H. L. , and van Hoesel , S. P. M. 2001 . Treewidth: Computational experiments. Tech. Rept. ZIB-Report 01-38, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin (ZIB). Koster, A. M. C. A., Bodlaender, H. L., and van Hoesel, S. P. M. 2001. Treewidth: Computational experiments. Tech. Rept. ZIB-Report 01-38, Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin (ZIB)."},{"volume-title":"Proceedings of the 10th Italian Symposium on Advanced Database Systems (SEBD).","author":"Leone N.","key":"e_1_2_1_11_1","unstructured":"Leone , N. , Mazzitelli , A. , and Scarcello , F . 2002. Cost-based query decompositions . In Proceedings of the 10th Italian Symposium on Advanced Database Systems (SEBD). Leone, N., Mazzitelli, A., and Scarcello, F. 2002. Cost-based query decompositions. In Proceedings of the 10th Italian Symposium on Advanced Database Systems (SEBD)."},{"volume-title":"Bucket elimination and hypertree decompositions. Implementation Rept","author":"McMahan B.","key":"e_1_2_1_12_1","unstructured":"McMahan , B. 2004. Bucket elimination and hypertree decompositions. Implementation Rept . Institute of Information Systems (DBAI) , TU Vienna. McMahan, B. 2004. Bucket elimination and hypertree decompositions. Implementation Rept. Institute of Information Systems (DBAI), TU Vienna."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.010"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1412229","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1412229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1412229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":12,"alternative-id":["10.1145\/1412228.1412229"],"URL":"https:\/\/doi.org\/10.1145\/1412228.1412229","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2009,2]]}}}