Approximating weighted matchings in parallel

Hougardy, S and Vinkemeier, DE ORCID: https://orcid.org/0000-0001-8767-4355, 2006. Approximating weighted matchings in parallel. Information Processing Letters, 99 (3), pp. 119-123. ISSN 0020-0190

Full text not available from this repository.

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:	Number Type 10.1016/j.ipl.2006.03.005 DOI 1849492 Other
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

Statistics

Views

Downloads