An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
| Autor: | Shibsankar Das |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Scientific Annals of Computer Science, Vol XXX, Iss 1, Pp 25-37 (2020) |
| Druh dokumentu: | article |
| ISSN: | 1843-8121 2248-2695 |
| DOI: | 10.7561/SACS.2020.1.25 |
| Popis: | 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,σ} . |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|