• search hit 6 of 28
Back to Result List

Improved Linear Time Approximation Algorithms for Weighted Matchings

Please always quote using this URN:urn:nbn:de:0296-matheon-1208
  • The weighted matching problem is to find a matching in a weighted graph that has maximum weight. The fastest known algorithm for this problem has running time O(nm +n2 log n). Many real world problems require graphs of such large size that this running time is too costly. We present a linear time approximation algorithm for the weighted matching problem with a performance ratio of 2 3 ???? ". This improves the previously best performance ratio of 1 2 .

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