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 timeO(n ω/2), whereω is the exponent of the best known matrix multiplication algorithm. Sinceω<2.38, this algorithm breaks through theO(n 1.5) barrier for the matching problem. This is the first result of this kind for general planar graphs. We also present an algorithm for generating perfect matchings in planar graphs uniformly at random usingO(n ω/2) arithmetic operations. Our algorithms are based on the Gaussian elimination approach to maximum matchings introduced in [16].
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