weighted-matching

Given a weighted bipartite graph G =(U,V,E) and a non-negative cost function C = cij associated with each edge (i,j)∈E, the problem of finding a match M ⊂ E such that minimizes ∑ cpq|(p,q) ∈ M, is a very important problem this problem is a classic example of Combinatorial Optimization, where a optimization problem is solved iteratively by solving an underlying combinatorial problem. This problem is also known as the assignment problem. The techniques developed in the Hungarian method assumes that the representation of the underlying bipartite graph is dense and thus emphasizes on the asymptotic complexity of computing the shortest augmenting path which is O((|V|+|U| +|E|)log(|V|+|U|)). However in practice this worst case asymptotic bound was never hit especially in case of the sparse representation of the underlying bipartite graph. In practice we found that the runtime (cputime) of the

SparsePreOrder
MeasureTime.h
MeasureTime.c
CompareAbs.c
Bipartite.cpp
MeasureTime.o
mc64
Bipartite_C.c
Heap.o
Heap.cpp
Makefile.windows
inplace_permute
Bipartite2.cpp
.deps
Makefile.gmake
CVS
bipartite1-sparc32
create_perm
win_bug.cpp
bipartite1-mc21-linux32
mc64.h
InPerm.txt
LogTest.c
Makefile
Bipartite_bcup.h
Makefile.bak
bipartite1-mc21-linux64
Bipartite.o
out
Makefile.Build.Solaris
ticks.txt
Bipartite_bcup.c
myutil
ReadSparse.o
bipartite1-linux64
pre.solaris.c
molex.out
bipartite1-mc21-sparc32
MC64Driver.c
mc64.out
bipartite1-sparc64
CreateMC64PermFile.c
ValidatePermutation.c
intel_mc64
run_ufl_tests.pl
PerlScripts
Bipartite.hpp
Bipartite.h
times.linux32.log
fdiff
FloatingFormat.c
mc64.diag
bipartite1-mc21-sparc64
DoubleHeap.c
RunDir
Heap.h
gmon.out
ReadSparse.c
dump_tran_matrices.pl
mc64_program
mm2rc.pl