Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Bounding Search Space Size via (Hyper)tree Decompositions
Lars Otten, Rina Dechter
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.
Keywords: null
Pages: 452-459
PS Link:
PDF Link: /papers/08/p452-otten.pdf
AUTHOR = "Lars Otten and Rina Dechter",
TITLE = "Bounding Search Space Size via (Hyper)tree Decompositions",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "452--459"

hosted by DSL   •   site info   •   help