Maximum matchings in planar graphs via gaussian elimination |
| |
Authors: | Marcin Mucha Piotr Sankowski |
| |
Affiliation: | (1) Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warsaw, Poland |
| |
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].
This research was supported by KBN Grant 4T11C04425. |
| |
Keywords: | Maximum matching Planar graphs Fast matrix multiplication |
本文献已被 SpringerLink 等数据库收录! |