Heuristic Methods for Hypertree Decompositions Export

@techreport{DerGanGotMcMMusSam2005, abstract = {In this paper we propose new algorithms for generating generalized hypertreedecompositions. The well known heuristics for generating tree decompositions based onvertex ordering have been extended to produce hypertree decompositions. We investigatethe generation of hypertree decompositions based on the tree decompositions of the primaland the dual graph of the hypergraph. Further, we propose a method for generatinghypertree decompositions using hypergraph partitioning. We use different algorithms forpartitioning hypergraphs. The proposed algorithms are experimentally evaluated in benchmarkproblems from the literature and industry. Using the proposed algorithms we improvethe best existing upper bounds for hypertree width for many problems.}, author = {Dermaku, Artan and Ganzow, Tobias and Gottlob, Georg and McMahan, Ben and Musliu, Nysret and Samer, Marko}, citeulike-article-id = {3072356}, citeulike-linkout-0 = {http://www.dbai.tuwien.ac.at/proj/hypertree/part.pdf}, keywords = {hypertree\_decomposition}, organization = {Technische Universit\"{a}t Wien}, posted-at = {2008-08-01 14:57:10}, priority = {5}, title = {Heuristic Methods for Hypertree Decompositions}, url = {http://www.dbai.tuwien.ac.at/proj/hypertree/part.pdf}, year = {2005} }

TY - RPRT ID - DerGanGotMcMMusSam2005 L3 - citeulike-article-id:3072356 N2 - In this paper we propose new algorithms for generating generalized hypertreedecompositions. The well known heuristics for generating tree decompositions based onvertex ordering have been extended to produce hypertree decompositions. We investigatethe generation of hypertree decompositions based on the tree decompositions of the primaland the dual graph of the hypergraph. Further, we propose a method for generatinghypertree decompositions using hypergraph partitioning. We use different algorithms forpartitioning hypergraphs. The proposed algorithms are experimentally evaluated in benchmarkproblems from the literature and industry. Using the proposed algorithms we improvethe best existing upper bounds for hypertree width for many problems. OR - Technische Universität Wien TI - Heuristic Methods for Hypertree Decompositions KW - hypertree_decomposition AU - Dermaku, Artan AU - Ganzow, Tobias AU - Gottlob, Georg AU - McMahan, Ben AU - Musliu, Nysret AU - Samer, Marko PY - 2005/// UR - http://www.dbai.tuwien.ac.at/proj/hypertree/part.pdf ER -