Bounding Search Space Size via (Hyper)tree Decompositions
  This paper develops a measure for bounding the performance of AND/OR search
algorithms for solving a variety of queries over graphical models. We show how
drawing a connection to the recent notion of hypertree decompositions allows to
exploit determinism in the problem specification and produce tighter bounds. We
demonstrate on a variety of practical problem instances that we are often able
to improve upon existing bounds by several orders of magnitude.
