Computer Science – Data Structures and Algorithms
Scientific paper
2003-06-23
Computer Science
Data Structures and Algorithms
5 pages, 2 figures
Scientific paper
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^2 \log{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^2$ and therefore the complexity is $O(n^3)$. In this paper we want to present a simple heuristic method to reduce the number of edges of complete bipartite graphs $G=(A \cup B,E)$ with $|A|=|B|$ such that $m = n\log{n}$ and therefore the complexity of such that $m = n\log{n}$ and therefore the complexity of $O(n^2 \log{n})$. The weights of all edges in G must be uniformly distributed in [0,1].
No associations
LandOfFree
Heuristic to reduce the complexity of complete bipartite graphs to accelerate the search for maximum weighted matchings with small error does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Heuristic to reduce the complexity of complete bipartite graphs to accelerate the search for maximum weighted matchings with small error, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Heuristic to reduce the complexity of complete bipartite graphs to accelerate the search for maximum weighted matchings with small error will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-513366