Content deleted Content added
→Definition: Added definition of symmetric difference between sets of edges |
→Algorithm: The introduction should correctly describe the algorithm |
||
Line 18:
== Algorithm ==
The Basic concept that the algorithm relies on is that if we have a matching N of size n, and P is the augmenting path relative to N, then the matching
Lets name the two sets in which G can be partitioned as U and V. The matching from U to V at any time is represented as the set M.
We also maintain a queue(first in first out datastructure) Q in our pseudo code.▼
The algorithm is run in phases. Each phase consists of:
* A BFS is run from free U vertices. This BFS stops at depth ''k'' where a free V vertex is reached. Note that, at the last iteration, the algorithm collects all free V vertices at depth ''k''.
* Find a maximal set of non-overlapping augmenting paths of length ''k''. Achieved by DFS from the free V vertices computed by BFS to free U vertices.
'''Work-in-progress'''. ''The following pseudo code does not describe this algorithm correctly. It has to be rewritten. Even worse, it requires O(n) iterations instead of <math>O(\sqrt{n})</math> as a result its complexity is O(n<sup>3</sup>) instead of O(n<sup>2.5</sup>)''
''Pseudo Code''
| |||