A Backtracking-Based Algorithm for Computing Hypertree-Decompositions
<|reference_start|>A Backtracking-Based Algorithm for Computing Hypertree-Decompositions: Hypertree 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.<|reference_end|>
@article{gottlob2007a,
    title={A Backtracking-Based Algorithm for Computing Hypertree-Decompositions},
    author={Georg Gottlob, Marko Samer},
    journal={ACM Journal of Experimental Algorithmics (JEA) 13(1):1.1-1.19,
  2008.},
    year={2007},
    doi={10.1145/1412228.1412229},
    archivePrefix={arXiv},
    eprint={cs/0701083},
    primaryClass={cs.DS cs.AI}
}