### A backtracking-based algorithm for hypertree decompositionA backtracking-based algorithm for hypertree decomposition

Access Restriction
Subscribed

 Author Gottlob, Georg ♦ Samer, Marko Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Constraint satisfaction ♦ Hypertree decomposition Abstract 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-\textit{k}-decomp$ for computing hypertree decompositions of small width. Our benchmark evaluations have shown that $det-\textit{k}-decomp$ significantly outperforms $opt-\textit{k}-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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-02-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 13 Page Count 19 Starting Page 1.1 Ending Page 1.19

#### Open content in new tab

Source: ACM Digital Library