Article ID Journal Published Year Pages File Type
429025 Information Processing Letters 2012 5 Pages PDF
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
, , ,