Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
On Heuristics for Finding Loop Cutsets in Multiply-Connected Belief Networks
Jonathan Stillman
Abstract:
We introduce a new heuristic algorithm for the problem of finding minimum size loop cutsets in multiply connected belief networks. We compare this algorithm to that proposed in [Suemmondt and Cooper, 1988]. We provide lower bounds on the performance of these algorithms with respect to one another and with respect to optimal. We demonstrate that no heuristic algorithm for this problem cam be guaranteed to produce loop cutsets within a constant difference from optimal. We discuss experimental results based on randomly generated networks, and discuss future work and open questions.
Keywords: null
Pages: 233-243
PS Link:
PDF Link: /papers/90/p233-stillman.pdf
BibTex:
@INPROCEEDINGS{Stillman90,
AUTHOR = "Jonathan Stillman ",
TITLE = "On Heuristics for Finding Loop Cutsets in Multiply-Connected Belief Networks",
BOOKTITLE = "Uncertainty in Artificial Intelligence 6 Annual Conference on Uncertainty in Artificial Intelligence (UAI-90)",
PUBLISHER = "Elsevier Science",
ADDRESS = "Amsterdam, NL",
YEAR = "1990",
PAGES = "233--243"
}


hosted by DSL   •   site info   •   help