Computing hypergraph width measures exactly

Details Computing hypergraph width measures exactly Computing hypergraph width measures exactly

2011-06-23

arxiv.org/abs/1106.4719v1

Computer Science

Computational Complexity

12 pages, 1 figure

Scientific paper

Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection between these and tree decompositions is established. This enables us to almost seamlessly adapt the combinatorial and algorithmic results known for tree decompositions of graphs to the case of hypergraphs and obtain fast exact algorithms. As a consequence, we provide algorithms which, given a hypergraph H on n vertices and m hyperedges, compute the generalized hypertree-width of H in time O*(2^n) and compute the fractional hypertree-width of H in time O(m*1.734601^n).

Affiliated with

Also associated with

No associations

Rating

Computing hypergraph width measures exactly 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 Computing hypergraph width measures exactly, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing hypergraph width measures exactly will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-469920