An \(O(\sqrt{|V|}\,|E|)\) Algorithm for Finding Maximum Matching in General Graphs

Micali, S., & Vazirani, V. V. (1980). An $O(\sqrt{|V|}\,|E|)$ Algorithm for Finding Maximum Matching in General Graphs. Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS), 17-27.

Type

Conference paper

Intellectual base

Primary research

Year

1980

DOI

10.1109/sfcs.1980.12

Link

https://doi.org/10.1109/SFCS.1980.12

Cited by

1 citation across 1 artifact.

Each citation links to the sentence it supports in the citing article.

Domain-specific

• Matching
  • Maximum matching on planar graphs is solvable in \(O(n^{3/2})\), since planarity forces \(|E| = O(n)\) by Euler's formula and the general Micali–Vazirani augmenting-path bound \(O(\sqrt{|V|}\,|E|)\) specialises accordingly

    This sourceEstablishes the $O(\sqrt{|V|}\,|E|)$ augmenting-path bound for maximum matching in general graphs, which is the general result this sentence specialises; the planar step itself — that Euler's formula forces $|E| = O(n)$, giving $O(n^{3/2})$ — is the entry's own arithmetic and is not a claim of this paper.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:0bfde92bbb7f · see in the full table