Löhnertz, Martin: Algorithmen für Matchingprobleme in speziellen Graphklassen. - Bonn, 2010. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5N-20399
@phdthesis{handle:20.500.11811/4528,
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5N-20399,
author = {{Martin Löhnertz}},
title = {Algorithmen für Matchingprobleme in speziellen Graphklassen},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2010,
month = mar,

note = {Das Matching- oder Korrespondenzproblem gehört zum Gebiet der Graphentheorie. Zielsetzung ist es, in einem Graphen mit n Knoten und m Kanten effizient ein maximales Matching, d.h. eine möglichst große Menge disjunkter Kanten zu finden. In dieser Arbeit stellen wir hierzu mehrere neue Algorithmen vor:
Erstens geben wir zwei Methoden an, um mit Hilfe von Graphenkompression, aber ohne Transformation in ein Flussproblem, ein maximales Matching in Zeit O(n^(0,5)m(log(2n^2/m)/log(n))) zu finden. Die eine Methode erlaubt einen einfachen Beweis ihrer Korrektheit, die andere ist aufgrund kleinerer Konstanten bei der Laufzeit eher zur Implementierung geeignet.
Zweitens präsentieren wir einen Algorithmus, der in einem bipartiten Graphen, der n^(0,5)o^3 disjunkte perfekte Matchings enthält, ein einzelnes maximales Matching in Zeit O(n^(0,5)m/o) findet.
Durch Kombination der beiden Verfahren können wir im zweiten Fall für spezielle Graphklassen noch weitere Verbesserungen erzielen.},

url = {http://hdl.handle.net/20.500.11811/4528}
}

The following license files are associated with this item:

InCopyright