Maximum Matchings in Planar Graphs via Gaussian Elimination

Marcin Mucha, Piotr Sankowski

Abstract

We present a randomized algorithm for finding maximum matchings in planar graphs in time O(n ω/2), where ω is the exponent of the best known matrix multiplication algorithm. Since ω< 2.38, this algorithm breaks through the O(n 1.5) barrier for the matching problem. This is the first result of this kind for general planar graphs.
BibTeX
@inproceedings{mucha2006maximum,
  author = {Marcin Mucha and Piotr Sankowski},
  title = {{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
  booktitle = {Algorithmica},
  year = {2006},
  url = {https://openreview.net/forum?id=YneBas4ofm},
}

Loading related content...

Figure