Heuristic to reduce the complexity of complete bipartite graphs to accelerate the search for maximum weighted matchings with small error

Daniel Etzold

A maximum weighted matching for bipartite graphs $G=(A\cup B,E)$ can be found by using the algorithm of Edmonds and Karp with a Fibonacci Heap and a modified Dijkstra in $O(nm + n…