Linear reductions of maximum matching

MaRDI QIDQ2768405zbMATH OpenFDO

Authors Therese Biedl

Publication date 16 April 2002

zbMATH Keywords

maximum matchingbiconnected graph3-regular graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs
• Maximum matching in regular and almost regular graphs
• Perfect matching for biconnected cubic graphs in \(O(n \log ^{2} n)\) time
• Computing large matchings fast
• scientific article; zbMATH DE number 1305400

Cited in

(3)

• Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
• Perfect matching for biconnected cubic graphs in \(O(n \log ^{2} n)\) time
• Efficient algorithms for Petersen's matching theorem

This page was built for publication: Linear reductions of maximum matching

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