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 problem-solving routines. We offer a novel approa
ch that guarantees removal of all redundancies that hide a tree struct
ure. We develop a polynomial-time algorithm that, given an arbitrary b
inary 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 latter case,
a tree is generated that may serve as an approximation to the original
network.