Complexity Analysis of Generalized and Fractional Hypertree Decompositions

Gottlob, Georg; Lanzinger, Matthias; Pichler, Reinhard; Razgon, Igor

doi:10.1145/3457374

All Outputs (5)

The splitting power of branching programs of bounded repetition and CNFs of bounded width (2024)
Journal Article
Razgon, I. (2025). The splitting power of branching programs of bounded repetition and CNFs of bounded width. Discrete Applied Mathematics, 360, 366-381. https://doi.org/10.1016/j.dam.2024.09.028

The Treewidth and Pathwidth of Graph Unions (2024)
Journal Article
Alecu, B., Lozin, V. V., Quiroz, D. A., Rabinovich, R., Razgon, I., & Zamaraev, V. (2024). The Treewidth and Pathwidth of Graph Unions. SIAM Journal on Discrete Mathematics, 38(1), 261-276. https://doi.org/10.1137/22m1524047

Fractional covers of hypergraphs with bounded multi-intersection (2023)
Journal Article
Gottlob, G., Lanzinger, M., Pichler, R., & Razgon, I. (2023). Fractional covers of hypergraphs with bounded multi-intersection. Theoretical Computer Science, 979, Article 114204. https://doi.org/10.1016/j.tcs.2023.114204

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our... Read More about Fractional covers of hypergraphs with bounded multi-intersection.

Tree-width dichotomy (2022)
Journal Article
Lozin, V., & Razgon, I. (2022). Tree-width dichotomy. European Journal of Combinatorics, 103, 103517. https://doi.org/10.1016/j.ejc.2022.103517

Complexity Analysis of Generalized and Fractional Hypertree Decompositions (2021)
Journal Article
Gottlob, G., Lanzinger, M., Pichler, R., & Razgon, I. (2021). Complexity Analysis of Generalized and Fractional Hypertree Decompositions. Journal of the ACM, 68(5), 1-50. https://doi.org/10.1145/3457374

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 conjunc... Read More about Complexity Analysis of Generalized and Fractional Hypertree Decompositions.