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

Original · EN

A maximum weighted matching for bipartite graphs G=(A ∪ 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² n) time where n is the number of nodes and m the number of edges. For the case that |A|=|B| the number of edges is n² and therefore the complexity is O(n³). In this paper we want to present a simple heuristic method to reduce the number of edges of complete bipartite graphs G=(A ∪ B,E) with |A|=|B| such that m = nn and therefore the complexity of such that m = nn and therefore the complexity of O(n² n). The weights of all edges in G must be uniformly distributed in [0,1].