Linear reductions of maximum matching

MaRDI QIDQ2768405zbMATH OpenFDO

Authors Therese Biedl

Publication date 16 April 2002

zbMATH Keywords

3-regular graphbiconnected graphmaximum matching

Mathematics Subject Classification ID

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

Review text

In 1999, \textit{T. C. Biedl, P. Bose, E. D. Demaine}, and \textit{A. Lubiw} [Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. Baltimore, MD, USA, January 17-19, 1999. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics, 130-139 (1999; Zbl 0938.68063)] showed how to find a perfect matching in a 3-regular biconnected graph of order \(n\) in \(O({\log}^4 n)\) time. In this note, which contains no proofs, the author discusses the question whether this algorithm can be extended to similar types of graphs, such as 3-regular graphs that are not biconnected.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].

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

(4)

• Efficient algorithms for Petersen's matching theorem
• Perfect matching for biconnected cubic graphs in \(O(n \log ^{2} n)\) time
• scientific article; zbMATH DE number 1305400 (Why is no real title available?)
• Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity

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)