Blossom algorithm: Difference between revisions

Revision as of 01:50, 29 April 2013

Revision as of 18:31, 6 July 2013

Line 166:

** 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 B21). 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

| title = An O(V^1/2E) algorithm for finding maximum matching in general graphs

| journalconference = 21st Annual Symposium on Foundations of Computer Science,

| year = 1980

| publisher = IEEE Computer Society Press, New York