Complexity Analysis of Generalized and Fractional Hypertree Decompositions
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Every hypergraph $H$ has a width relative to each of these methods: …