An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
Shibsankar Das · Scientific Annals of Computer Science · 2020
The problem of computing a maximum weight matching in a bipartite graph is one of the fundamental algorithmic problems that has played an important role in the development of combinatorial optimization and algorithmics.Let G w,σ is a collection of all weighted bipartite graphs, each having σ and w as the size of each of the non-empty subset of the vertex partition and the total weight of the graph, respectively.We give a tight lower bound w-σ σ + 1 for the set {Wt(mwm(G)) | G ∈ G w,σ } which denotes the collection of weights of maximum weight bipartite matchings of all the graphs in G w,σ .