Donald Bren School of Information and Computer Sciences

This paper studies the possibility of removing redundant information from a given knowledge base and restructuring it in the form of a tree to enable efficient problem solving routines. We offer a novel approach that guarantees removal of all redundancies that hide a tree structure. We develop a polynomial-time algorithm that, given an arbitrary constraint network, either extracts (by edge removal) a precise tree representation from the path-consistent version of the network or acknowledges that no such tree cari be extracted. In the event of the latter, the tree generated may serve as a good approximation to the original network.