CE653 - PTnet Theory and some Algorithms

Algorithm Find_All_Min_Siphons(G, ~P, P)

SS = Ø; // Minimal Siphon Set //

while ((~P == Ø) && (exists p in P such that •p = Ø)) {

S = {p}; SS = SS U {S}; G = red(G, P – {p}); // Rule 2 //

}

~S = Find_Siphon(G, ~P, P);

if (~S == Ø) return;

S = Find_Min_Siphon(G, ~S, ~P, P);

SS = SS U S;

Pnew = S - ~P; Pold = Ø;

if (Pnew == Ø) return;

forall (p in Pnew) {

Gp = red(G, P – {p});

SSp = Find_All_Min_Siphons(Gp, ~P U Pold, P); // Rule 7 //

SS = SS U SSp;

Pnew = Pnew – {p}; Pold = Pold U {p};

}

Find all Minimal Siphons - Algorithn

20/3/2014

CE-653 - PTnet Theory and some Algorithms

}Find_All_Min_Siphons(G, Ø) returns all minimal siphons of G

}Worst-case complexity is O(2n)

}Due to Recursive call for Rule 7