A simple approximation algorithm for the weighted matching problem |
| |
| Authors: | Doratha E Drake |
| |
| Affiliation: | Institut für Informatik, Humboldt-Universität zu Berlin, 10099 Berlin, Germany |
| |
| Abstract: | We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time. |
| |
| Keywords: | Approximation algorithms Analysis of algorithms Graph algorithms Maximum weight matching |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
