Blossom algorithm: Difference between revisions

Revision as of 15:49, 3 January 2014

Revision as of 15:50, 3 January 2014

Line 168:

** every exposed vertex in ''G'' is a root of an alternating tree in ''F''.

Each iteration of the loop starting at line B09 either adds to a tree ''T'' in ''F'' (line B10) or finds an augmenting path (line B17) or finds a blossom (line B21B20). It is easy to see that the running time is <math>O( |V|^4 )</math>. Micali and Vazirani<ref name = "micali">{{cite conference

| author1 = Micali, Silvio

| author2 = Vazirani, Vijay