The Algorithm in Terms of Bipartite Graphs
During the algorithm we maintain a potential y and an orientation of (denoted by ) which has the property that the edges oriented from T to S form a matching M. Initially, y is 0 everywhere, and all edges are oriented from S to T (so M is empty). In each step, either we modify y so that its value increases, or modify the orientation to obtain a matching with more edges. We maintain the invariant that all the edges of M are tight. We are done if M is a perfect matching.
In a general step, let and be the vertices not covered by M (so consists of the vertices in S with no incoming edge and consists of the vertices in T with no outgoing edge). Let be the set of vertices reachable in from by a directed path only following edges that are tight. This can be computed by breadth-first search.
If is nonempty, then reverse the orientation of a directed path in from to . Thus the size of the corresponding matching increases by 1.
If is empty, then let . is positive because there are no tight edges between and . Increase y by on the vertices of and decrease y by on the vertices of . The resulting y is still a potential. The graph changes, but it still contains M. We orient the new edges from S to T. By the definition of the set Z of vertices reachable from increases (note that the number of tight edges does not necessarily increase).
We repeat these steps until M is a perfect matching, in which case it gives a minimum cost assignment. The running time of this version of the method is : M is augmented n times, and in a phase where M is unchanged, there are at most n potential changes (since Z increases every time). The time needed for a potential change is .
Read more about this topic: Hungarian Algorithm
Famous quotes containing the word terms:
“In colonial America, the father was the primary parent. . . . Over the past two hundred years, each generation of fathers has had less authority than the last. . . . Masculinity ceased to be defined in terms of domestic involvement, skills at fathering and husbanding, but began to be defined in terms of making money. Men had to leave home to work. They stopped doing all the things they used to do.”
—Frank Pittman (20th century)