Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
From MaRDI portal
Publication:751274
DOI10.1016/0020-0190(91)90195-NzbMath0714.68036WikidataQ56626048 ScholiaQ56626048MaRDI QIDQ751274
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases, Trapezoid graphs and generalizations, geometry and algorithms, An O(\(n\)) time algorithm for maximum matching on cographs, A linear time algorithm for the maximum matching problem on cographs, Persistency in maximum cardinality bipartite matchings, Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem, Solution methods and computational investigations for the linear bottleneck assignment problem, Multiple bottleneck assignment problem, Weakly Hamiltonian-connected ordinary multipartite tournaments, Alternating paths in edge-colored complete graphs, Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs, Algorithms for dense graphs and networks on the random access computer, OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS
