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

Pages

17-27

DOI

10.1109/sfcs.1980.12

DOI registrant

Institute of Electrical and Electronics Engineers

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

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Not recorded. The single citation of this work carries no recorded support check.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

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