• search hit 7 of 28
Back to Result List

Linear Time Local Improvements for Weighted Matchings in Graphs

Please always quote using this URN:urn:nbn:de:0296-matheon-1218
  • Recently two different linear time approximation algorithms for the weighted matching problem in graphs have been suggested [5][17]. Both these algorithms have a performance ratio of 1/2. In this paper we present a set of local improvement operations and prove that it guarantees a performance ratio of 2/3. We show that a maximal set of these local improvements can be found in linear time. To see how these local improvements behave in practice we conduct an experimental comparison of four different approximation algorithms for calculating maximum weight matchings in weighted graphs. One of these algorithms is the commonly used Greedy algorithm which achieves a performance ratio of 1/2 but has O(m log n) runtime. The other three algorithms all have linear runtime. Two of them are the above mentioned 1/2 approximation algorithms. The third algorithm may have an arbitrarily bad performance ratio but in practice produces reasonably good results. We compare the quality of the algorithms on a test set of weighted graphs and study the improvement achieved by our local improvement operations. We also do a comparison of the runtimes of all algorithms.

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-1218
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:150
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.