Topological Parameters for Time-Space Trade-Off

In this paper we propose a family of algorithms combining treeclustering 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 demonstrate how the tradeoffs associated with various hybrids can be explicated and be used for each problem instance