Zwei approximative Algorithmen für das Matchingproblem in gewichteten Graphen
Please always quote using this URN:urn:nbn:de:0296-matheon-2866
- Es werden zwei approximative Algorithmen zum Matchingproblem für gewichtete Graphen vorgestellt. Der eine erreicht Güte 2/3-epsilon in Laufzeit O(m+n), der andere 3/4-epsilon in Laufzeit O((m+n)log n).
Author: | Sven Hanke |
---|---|
URN: | urn:nbn:de:0296-matheon-2866 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | German |
Date of first Publication: | 2005/05/11 |
Release Date: | 2005/10/31 |
Preprint Number: | 271 |