Abstract
The paper provides a unifying perspective of tree-decomposition algorithms appearing in various automated reasoning areas such as join-tree clustering for constraint-satisfaction and the clique-tree al- gorithm for probabilistic reasoning. Within this framework, we in- troduce a new algorithm, called bucket-tree elimination (BTE), that extends Bucket Elimination (BE) to trees, and show that it can pro- vide a speed-up of n over BE for various reasoning tasks. Time-space tradeoŽs of tree-decomposition processing are analyzed.