The Hungarian algorithm finds a maximum independent edge set on a graph. The algorithm starts with any matching M and constructs a tree via a breadth-first search to find an augmenting path, namely a path P that starts and finishes at unmatched vertices whose first and last edges are not in M and whose edges alternate being outside and inside M. If the search succeeds, the symmetric difference of M and the edges in P yields a matching with one more edge than M. That edge is added, and then another search is performed for a new augmenting path. If the search is unsuccessful, the algorithm terminates and M must be the largest-size matching. As an added bonus, the tree data provides a vertex cover.

augmenting path | blossom algorithm | matching | matching number | maximum independent edge set

Hungary