Autor(en): | Schoppmeyer, Andreas |
Titel: | On computing maximum size matchings in graphs |
Sprache (ISO): | en |
Zusammenfassung: | The problem of finding a maximum-size matching in a graph appears in many situations in graph theory. Therefore it is crucial to compute such matchings in a fast way. In some cases a hybrid algorithm, consisting of an heuristic to find a start-matching and an exact algorithm to compute the maximum-size matching, appears to be much faster than classical algorithms. We show a way to implement appropriate heuristics, exact algorithms and hybrid algorithms in C++ and compare their performance on different random graphs. To reduce the programming-effort , we used comprehensible techniques. These techniques can be implemented indepen- dent of programming languages and the operating systems. |
Schlagwörter: | Efficient graph algoritms Maximun-size matchings |
URI: | http://hdl.handle.net/2003/23117 http://dx.doi.org/10.17877/DE290R-3076 |
Erscheinungsdatum: | 2006 |
Provinienz: | Universität Dortmund, Wirtschafts- und Sozialwissenschaftliche Fakultät |
Enthalten in den Sammlungen: | Fachgebiet Operations Research und Wirtschaftsinformatik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
SchoppmeyerAndreasdispap32.pdf | DNB | 90.11 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org