Authors: | Schoppmeyer, Andreas |
Title: | On computing maximum size matchings in graphs |
Language (ISO): | en |
Abstract: | 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. |
Subject Headings: | Efficient graph algoritms Maximun-size matchings |
URI: | http://hdl.handle.net/2003/23117 http://dx.doi.org/10.17877/DE290R-3076 |
Issue Date: | 2006 |
Provenance: | Universität Dortmund, Wirtschafts- und Sozialwissenschaftliche Fakultät |
Appears in Collections: | Fachgebiet Operations Research und Wirtschaftsinformatik |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
SchoppmeyerAndreasdispap32.pdf | DNB | 90.11 kB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is protected by original copyright rightsstatements.org