Beyond Hypertree Width: Decomposition Methods Without Decompositions

Details Beyond Hypertree Width: Decomposition Methods Without Decompositions Beyond Hypertree Width: Decomposition Methods Without Decompositions

2005-05-12

arxiv.org/abs/cs/0505035v1

Computer Science

Computational Complexity

Scientific paper

The general intractability of the constraint satisfaction problem has motivated the study of restrictions on this problem that permit polynomial-time solvability. One major line of work has focused on structural restrictions, which arise from restricting the interaction among constraint scopes. In this paper, we engage in a mathematical investigation of generalized hypertree width, a structural measure that has up to recently eluded study. We obtain a number of computational results, including a simple proof of the tractability of CSP instances having bounded generalized hypertree width.

Affiliated with

Also associated with

No associations

Rating

Beyond Hypertree Width: Decomposition Methods Without Decompositions 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 Beyond Hypertree Width: Decomposition Methods Without Decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beyond Hypertree Width: Decomposition Methods Without Decompositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162845