Editing Matching (graph theory) (section)

=== Maximum-weight matching ===
{{Main|Maximum weight matching}}
In a [[weighted graph|''weighted'']] ''bipartite graph,'' the optimization problem is to find a maximum-weight matching; a dual problem is to find a minimum-weight matching. This problem is often called '''maximum weighted bipartite matching''', or the '''[[assignment problem]]'''. The [[Hungarian algorithm]] solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. It uses a modified [[shortest path]] search in the augmenting path algorithm. If the [[Bellman–Ford algorithm]] is used for this step, the running time of the Hungarian algorithm becomes <math>O(V^2 E)</math>, or the edge cost can be shifted with a potential to achieve <math>O(V^2 \log{V} + V E)</math> running time with the [[Dijkstra algorithm]] and [[Fibonacci heap]].<ref name="Fredman87">{{citation|last1=Fredman|first1=Michael L.|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=[[Journal of the ACM]]|volume=34|issue=3|pages=596–615|year=1987|doi=10.1145/28869.28874|last2=Tarjan|first2=Robert Endre|s2cid=7904683|doi-access=free}}</ref>

In a ''non-bipartite weighted graph'', the problem of '''[[maximum weight matching]]''' can be solved in time  <math>O(V^{2}E)</math> using [[Edmonds's matching algorithm|Edmonds' blossom algorithm]].