Maximum Matchings in Planar Graphs via Gaussian Elimination
Lists
Only you see this
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...