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
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 SizeFormat 
SchoppmeyerAndreasdispap32.pdfDNB90.11 kBAdobe PDFView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.