Maximum matching of given weight in complete and complete bipartite graphs

DOI10.1007/BF01068796zbMath0688.05070OpenAlexW1986282076MaRDI QIDQ4206784

Alexander V. Karzanov

Publication date: 1987

Published in: Cybernetics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01068796

zbMATH Keywords

polynomial algorithmmaximum matchingbottleneck matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

Related Items (16)

Matchings in colored bipartite networks ⋮ Knapsack problem with objective value gaps ⋮ Simple paths with exact and forbidden lengths ⋮ Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms ⋮ A weighted perfect matching with constraints on weights of its parts ⋮ Integrality gaps for colorful matchings ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ On generalized balanced optimization problems ⋮ Filling crosswords is very hard ⋮ Minimizing the number of late jobs on a single machine under due date uncertainty ⋮ Finding the set of alternatives in discrete multicriterion problems ⋮ A polynomial time equivalence between DNA sequencing and the exact perfect matching problem ⋮ Bicolored matchings in some classes of graphs ⋮ Cooperation in Multiorganization Matching ⋮ Adjacency on the constrained assignment problem

Cites Work

• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item

This page was built for publication: Maximum matching of given weight in complete and complete bipartite graphs