Topological parameters for time-space tradeoff

In this paper we propose a family of algorithms combining tree-clustering with conditioning that trade space for time. Such algorithms are useful for reasoning in probabilistic and deterministic networks as well as for accomplishing optimization tasks. By analyzing the problem structure, the user can select from a spectrum of algorithms, the one that best meets a given time-space specification. To determine the potential of this approach we analyze the structural properties of problems coming from the circuit diagnosis domain. The analysis demonstrates how the tradeoffs associated with various hybrids can be used for each problem instance. (C) 2001 Elsevier Science B.V. All rights reserved.