Reducing redundancy in the hypertree decomposition scheme

Authors

Peter HarveyFollow
Aditya K. Ghose, University of WollongongFollow

RIS ID

9576

Publication Details

This paper originally appeared as: Harvey, P and Ghose, A, Reducing redundancy in the hypertree decomposition scheme, Proceedings. 15th IEEE International Conference on Tools with Artificial Intelligence, 3-5 November 2003, 474-481. Copyright IEEE 2003.

Abstract

Hypertree decomposition is a powerful technique for transforming near-acyclic CSPs into acyclic CSPs. Acyclic CSPs have efficient, polynomial time solving techniques, and so these conversions are of interest to the constraints community. We present here an improvement on the opt-k-decomp algorithm for finding an optimal hypertree decomposition.