2003/06/23 by Daniel Etzold, Etzold, Daniel
Computer Science · Engineering · #Data Management and Algorithms #Graph Theory and Algorithms #Vehicle Routing Optimization Methods #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0306123
5 pages, 2 figures
arxiv created 2003/06/23 · arxiv updated 2009/11/30
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 + n2 logn) 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 n2 and therefore the complexity is O(n3). 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 = nlogn and therefore the complexity of such that m = nlogn and therefore the complexity of O(n2 logn). The weights of all edges in G must be uniformly distributed in [0,1].