A Backtracking-Based Algorithm for Computing Hypertree-Decompositions

Simple item page
dc.creatorGottlob, Georg
dc.creatorSamer, Marko
dc.date2007-01-14
dc.date.accessioned2026-07-07T10:08:55Z
dc.date.available2026-07-07T10:08:55Z
dc.descriptionHypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the cyclicity and therefore tractability of the encoded computation problem. Many NP-hard decision and computation problems are known to be tractable on instances whose structure corresponds to hypergraphs of bounded hypertree-width. Intuitively, the smaller the hypertree-width, the faster the computation problem can be solved. In this paper, we present the new backtracking-based algorithm det-k-decomp for computing hypertree decompositions of small width. Our benchmark evaluations have shown that det-k-decomp significantly outperforms opt-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 not too large.
dc.description19 pages, 6 figures, 3 tables
dc.identifierhttps://arxiv.org/abs/cs/0701083
dc.identifierhttp://arxiv.org/abs/cs/0701083
dc.identifierACM Journal of Experimental Algorithmics (JEA) 13(1):1.1-1.19, 2008.
dc.identifierdoi:10.1145/1412228.1412229
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/171165
dc.subjectData Structures and Algorithms
dc.subjectArtificial Intelligence
dc.subjectI.2.8
dc.titleA Backtracking-Based Algorithm for Computing Hypertree-Decompositions
dc.typetext

Files

Collections

arXiv