An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs

DOI10.7561/SACS.2020.1.25OpenAlexW3081541876MaRDI QIDQ5089613FDOQ5089613

Authors Shibsankar Das 

Publication date 19 July 2022

Published in Scientific Annals of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.00406

zbMATH Keywords

combinatorial optimizationbipartite graphstring matchingmaximum weight bipartite matchinglower bound for weights of bipartite matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Optimum matchings in weighted bipartite graphs
• Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
• Maximum matching of given weight in complete and complete bipartite graphs
• Maximum weight induced matching in some subclasses of bipartite graphs
• A scaling algorithm for maximum weight matching in bipartite graphs
• Matchings in node-weighted convex bipartite graphs
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• A decomposition theorem for maximum weight bipartite matchings
• A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
• A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings

Cited In (8)

• Optimum matchings in weighted bipartite graphs
• Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching
• Title not available (Why is no real title available?)
• Maximum matching of given weight in complete and complete bipartite graphs
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• A decomposition theorem for maximum weight bipartite matchings

This page was built for publication: An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089613)