Tools
Tools
Hougardy, S. and Vinkemeier, D.E. 
ORCID: 0000-0001-8767-4355,
2006.
Approximating weighted matchings in parallel.
Information Processing Letters, 99 (3), pp. 119-123.
ISSN 0020-0190
Official URL: https://doi.org/10.1016/j.ipl.2006.03.005
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 (1/2−ε) of an NC algorithm for this problem.
| Item Type: | Journal article | ||||||
|---|---|---|---|---|---|---|---|
| Publication Title: | Information Processing Letters | ||||||
| Creators: | Hougardy, S. and Vinkemeier, D.E. | ||||||
| Publisher: | Elsevier BV | ||||||
| Date: | August 2006 | ||||||
| Volume: | 99 | ||||||
| Number: | 3 | ||||||
| ISSN: | 0020-0190 | ||||||
| Identifiers: |
|
||||||
| Divisions: | Schools > School of Science and Technology | ||||||
| Record created by: | Jeremy Silvester | ||||||
| Date Added: | 04 Jan 2024 09:37 | ||||||
| Last Modified: | 04 Jan 2024 09:37 | ||||||
| URI: | https://irep.ntu.ac.uk/id/eprint/50616 |
Actions (login required)
 |
Edit View |
Views
Views per month over past year
Downloads
Downloads per month over past year
