Tree Decomposition with Applications to Constraint Processing

Itay Meiri, Rina Dechter, Judea Pearl

This paper concerns the task of removing redundant information from a given knowledge base, and restructuring it in the form of a tree, so as to admit efficient problem solving routines. We offer a novel approach which guarantees the removal of all redundancies that hide a tree structure. We develop a polynomial time algorithm that, given an arbitrary constraint network, generates a precise tree representation whenever such a tree can be extracted from the input network, otherwise, the fact that no tree representation exists is acknowledged, and the tree generated may serve as a good approximation to the original network.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.