• search hit 8 of 28
Back to Result List

A Simple Approximation Algorithm for the Weighted Matching Problem

Please always quote using this URN:urn:nbn:de:0296-matheon-1228
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Doratha E. Drake, Stefan Hougardy
URN:urn:nbn:de:0296-matheon-1228
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2004/09/19
Release Date:2004/04/19
Institute:Humboldt-Universität zu Berlin
Preprint Number:151
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.