A fast dynamic optimum algorithm for maximum matching in bipartite graphs

MaRDI QIDQ5199685zbMATH OpenFDO

Authors Jingang Zhai, Hongbo Li

Publication date 16 August 2011

Full work available at URL http://en.cnki.com.cn/Article_en/CJFDTOTAL-WOOD200603002.htm

zbMATH Keywords

bipartite graphs maximum matching

Mathematics Subject Classification ID

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

Recommendations

• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Fully dynamic matching in bipartite graphs
• Finding all maximally-matchable edges in a bipartite graph
• An optimal parallel algorithm for maximal matching
• A simple matching algorithm for regular bipartite graphs.

Cited in

(11)

• Maximum matchings of a digraph based on the largest geometric multiplicity
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• scientific article; zbMATH DE number 5909229 (Why is no real title available?)
• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• scientific article; zbMATH DE number 67678 (Why is no real title available?)
• Finding all maximally-matchable edges in a bipartite graph
• scientific article; zbMATH DE number 1054930 (Why is no real title available?)
• A Competitive Strong Spanning Tree Algorithm for the Maximum Bipartite Matching Problem
• A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
• scientific article; zbMATH DE number 6299967 (Why is no real title available?)
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)

This page was built for publication: A fast dynamic optimum algorithm for maximum matching in bipartite graphs

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