A backtracking-based algorithm for hypertree decomposition Export

@article{GotSam2009, 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- 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 sufficiently simple.}, address = {New York, NY, USA}, author = {Gottlob, Georg and Samer, Marko}, citeulike-article-id = {5683680}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1412228.1412229}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1412228.1412229}, doi = {10.1145/1412228.1412229}, issn = {1084-6654}, journal = {J. Exp. Algorithmics}, keywords = {confirmation, pods10}, posted-at = {2009-08-29 22:57:46}, priority = {5}, publisher = {ACM}, title = {A backtracking-based algorithm for hypertree decomposition}, url = {http://dx.doi.org/10.1145/1412228.1412229}, volume = {13}, year = {2009} }

TY - JOUR ID - GotSam2009 L3 - citeulike-article-id:5683680 N2 - 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- 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 sufficiently simple. JF - J. Exp. Algorithmics SN - 1084-6654 AD - New York, NY, USA TI - A backtracking-based algorithm for hypertree decomposition PB - ACM VL - 13 KW - confirmation KW - pods10 AU - Gottlob, Georg AU - Samer, Marko PY - 2009/// UR - http://dx.doi.org/10.1145/1412228.1412229 ER -