Posted by Laura Kruse on February 11, 2001 at 20:27:19:
In Reply to: Re: LS Algorithm - source of error posted by Haipeng Guo on February 11, 2001 at 20:24:14:
Here's my 2 cents....
This was the algorithm that Dr. Hsu said was the fix...the line way at the bottom says
S += {clique} // S := S \ {union} clique
Which in my mind, means you just keep adding things to S as you go along. And that's what I thought I got out of Neapolitan... I don't have
my Neapolitan copy no more because I gave that to John to give to Julie...
But that's my two cents...
Here's the algorithm (my solution to Exercise 3.2.3 Neapolitan - please refer to it and Chapter 3 if this is not clear):
GIVEN: a triangulated graph (V, E) with a max cardinality ordering, alpha
FIND: the clique set S
1. Order vertices according to alpha = {v_1, v_2, ..., v_n}
2. for v = v_1 to v_n
clique = findCliqueWith (V, E, v);
for each u in clique
if u's neighbors are all in clique // see NOTE below!
E -= {edges with u as an endpoint} // E := E \diff u-edges
S += {clique} // S := S \union {clique}
3. return s
Laura