|
|||||
|
|
Approximating weighted matchings in parallel |
|
| Authors: | Stefan Hougardy Doratha E. Vinkemeier |
| Affiliation: | Humboldt-Universität zu Berlin, Institut für Informatik, 10099 Berlin, Germany |
| Abstract: | We present an NC approximation algorithm for the weighted matching problem in graphs with an approximation ratio of (1−ε). This improves the previously best approximation ratio of  of an NC algorithm for this problem. |
| Keywords: | Approximation algorithms Parallel algorithms Analysis of algorithms Graph algorithms Maximum weight matching |
| 本文献已被 ScienceDirect 等数据库收录！ | |