On Heuristics for Finding Loop Cutsets in Multiply-Connected Belief
  Networks
  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.
