Content deleted Content added
Rescuing 1 sources and tagging 0 as dead. #IABot (v1.4.2) |
Changed run time complexity from |V|^4 to |E||V|^2, the complexity proof can be found in Edmonds work or any typical paper about this algorithm. |
||
Line 177:
** 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 B20). It is easy to see that the running time is <math>O( |E||V|^
| author1 = Micali, Silvio
| author2 = Vazirani, Vijay
| |||