Perfect matchings and extended polymatroid

DOI10.1007/S10559-008-9013-0zbMATH Open1144.05053OpenAlexW2015524385MaRDI QIDQ946789FDOQ946789

Authors: F. A. Sharifov 

Publication date: 24 September 2008

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-008-9013-0

Recommendations

• Perfect matching and polymatroids
• Perfectly matchable subgraph problem on a bipartite graph
• A polynomial algorithm for the extendability problem in bipartite graphs

zbMATH Keywords

bipartite graphperfect matchingextended polymatroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Selected topics on assignment problems
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Signature Methods for the Assignment Problem
• Minimum cut problem using bases of extended polymatroids

Cited In (6)

• Title not available (Why is that?)
• New variants of perfect non-crossing matchings
• Matching Problems in Polymatroids Without Double Circuits
• Cluster expansion formulas and perfect matchings
• Perfectly matchable subgraph problem on a bipartite graph
• Perfect matching and polymatroids

This page was built for publication: Perfect matchings and extended polymatroid

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