|
R44a
Topological Parameters For Time-Space Tradeoff
Rina Dechter (dechter@ics.uci.edu), Yousri El Fattah

Abstract
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 optimization tsks. By analyzing the problem structure the user can select from a spectrum of hybrid algorithms, the on that best meets a giben time-space specification. To determine the potential of this approach, we analyze the structural prperties of problems coming from the circuit diagnosis domain. The analysis demonstrate ho the tradeoffs associated with various hybrids can beexplicated and be used for each problem instance.

[pdf]