Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429025 | Information Processing Letters | 2012 | 5 Pages |
Abstract
Hypergraph width measures are important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. As a consequence, we obtain algorithms which, for a hypergraph H on n vertices and m hyperedges, compute its generalized hypertree-width in time O⁎(n2)O⁎(2n) and its fractional hypertree-width in time O(n1.734601⋅m)O(1.734601n⋅m).3
► We present a general exact exponential algorithm for the f-width of a hypergraph. ► Our algorithm works for any monotone width function f. ► This results in the currently fastest algorithm for generalized hypertree-width. ► Also this results in the currently fastest algorithm for fractional hypertree-width.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Lukas Moll, Siamak Tazari, Marc Thurley,