Computer Science – Data Structures and Algorithms
Scientific paper
2007-01-14
ACM Journal of Experimental Algorithmics (JEA) 13(1):1.1-1.19, 2008.
Computer Science
Data Structures and Algorithms
19 pages, 6 figures, 3 tables
Scientific paper
10.1145/1412228.1412229
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.
Gottlob Georg
Samer Marko
No associations
LandOfFree
A Backtracking-Based Algorithm for Computing Hypertree-Decompositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Backtracking-Based Algorithm for Computing Hypertree-Decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Backtracking-Based Algorithm for Computing Hypertree-Decompositions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-122109