|
R12
Uncovering Trees In Constraint Networks
Rina Dechter (dechter@ics.uci.edu), Itay Meiri (itay@cs.ucla.edu) & Judea Pearl (judea@cs.ucla.edu)

Abstract
This paper examines the possibility of removing redundant information from a given knowledge base and restructuring it in the form of a tree to enable efficient problemsolving 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 binary 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 can be extracted. In the the latter case, a tree is generated that may serve as an approximation to the original network.

  [ps] [pdf]