Linear reductions of maximum matching (Q2768405)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Linear reductions of maximum matching |
scientific article; zbMATH DE number 1699323
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Linear reductions of maximum matching |
scientific article; zbMATH DE number 1699323 |
Statements
16 April 2002
0 references
maximum matching
0 references
biconnected graph
0 references
3-regular graph
0 references
Linear reductions of maximum matching (English)
0 references
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].
0 references
