A Tight Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs

Abstract

Let $\Ga$ be the collection of all weighted bipartite graphs each having $\sigma$ and $m$, as the size of a vertex partition and the total weight, respectively. We give a tight lower bound $\lceil \frac{m-\sigma }{\sigma }\rceil +1$ for the set $\{\textit{Wt}(\textit{mwm}(G))~|~G \in \Ga\}$ which denotes the collection of weights of maximum weight bipartite matchings of all graphs in $\Ga$.

arXiv comment10 pages, 3 figures

Cited by in corpus (1)

• Experimental Evaluation of Modified Decomposition Algorithm for Maximum Weight Bipartite Matching