On computing maximum size matchings in graphs
Loading...
Date
2006
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universität Dortmund, Wirtschafts- und Sozialwissenschaftliche Fakultät
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.
Description
Table of contents
Keywords
Efficient graph algoritms, Maximun-size matchings