
| MGA WRA   |    |         |      |    |
|-----------|----|---------|------|----|
| V         | E  | val ues | size | Eq |

Fig ure Number of graphs in which MGA or WRA yield a smaller loop cutset  The last column records the number of graphs for which the two algorithms produced loop cutsets of the same weight Each line in the table is based on graphs

F F' M m n  Max, c  w (F)
End While Return F
Theorem 6 If Max > c k, where k is the minimal size of a minimum WFVS of an undirected weighted graph G, then WRA(G, c, Max) outputs a minimum WFVS of G with probability at least The proof is an immediate corollary of Theorem The choice of Max and c depend on the application  A decision theoretic approach for selecting such values for any time algorithms is discussed by Breese and Horvitz

## 4. Experimental Results

The experiments compared the outputs of WRA vis a vis a greedy algorithm GA and a modified greedy algorithm MGA  Becker   Geiger       based on randomly generated graphs and on some real graphs contributed by the Hugin group www hugin com The random graphs are divided into three sets  Graphs with    vertices and edges where the number of values associated with each vertex is randomly chosen between and and between  and    Graphs with   vertices and    edges where the number and of values associated with each vertex is randomly chosen between and and and Graphs with - vertices and - edges where the number of values between and as a strength of the Each instance of the three classes is based on    random graphs generated as described by Suermondt and Cooper The total number of random graphs we used is The results are summanzed in the table of Figure WRA is run with Max and The two algorithms MGA and WRA output loop cutsets of the same size in only C