Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 21, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Claudia Käppeli
I will present a randomized algorithm for finding maximum matchings in general graphs. The algorithm has running time O(nw), where w is the exponent of the best known matrix multiplication algorithm. Since w < 2.38, this algorithm breaks through the O(n2.5) barrier for the matching problem.
Marcin Mucha and Piotr Sankowski, "Maximum Matchings via Gaussian Elimination", FOCS 2004, pp. 248-257.
Automatic MiSe System Software Version 1.4803M | admin login