Persistency in maximum cardinality bipartite matchings

DOI10.1016/0167-6377(94)90049-3zbMath0810.90126OpenAlexW2061687898MaRDI QIDQ1332944

Marie-Christine Costa

Publication date: 5 September 1994

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(94)90049-3

zbMATH Keywords

undirected bipartite graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Optimum matchings in weighted bipartite graphs, Constraint programming and operations research, A polynomial algorithm for the extendability problem in bipartite graphs, Generalised arc consistency for the AllDifferent constraint: an empirical survey, Safety and completeness in flow decompositions for RNA assembly, Global constraint catalogue: past, present and future, Simplicity in Eulerian circuits: uniqueness and safety, Finding all maximally-matchable edges in a bipartite graph, Persistency in combinatorial optimization problems on matroids, Persistency and matroid intersection, Persistency in the assignment and transportation problems, Safety in \(s\)-\(t\) paths, trails and walks

Cites Work

• Unnamed Item
• Unnamed Item
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Matching theory
• The uniquely solvable bipartite matching problem
• Efficient algorithms for finding maximum matching in graphs
• Rank of maximum matchings in a graph