Optimum matchings in weighted bipartite graphs

DOI10.1007/s40590-015-0065-7zbMath1333.05299arXiv1403.5606OpenAlexW1922567740MaRDI QIDQ265439

Carlos E. Valencia, Marcos C. Vargas

Publication date: 4 April 2016

Published in: Boletín de la Sociedad Matemática Mexicana. Third Series (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphmatchingassignment problemoptimum matchingweighted bipartite graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding all maximally-matchable edges in a bipartite graph
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Scaling algorithms for network problems
• Auction algorithms for network flow problems: A tutorial introduction
• Finding all the perfect matchings in bipartite graphs
• Persistency in maximum cardinality bipartite matchings
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An efficient cost scaling algorithm for the assignment problem
• Assignment Problems
• Faster Scaling Algorithms for Network Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Optimum matchings in weighted bipartite graphs