Algorithmen für Matchingprobleme in speziellen Graphklassen
Algorithmen für Matchingprobleme in speziellen Graphklassen
Dokument öffnen (1.4MB)Art der Hochschulschrift
DissertationPrüfungsdatum
03.02.2010Datum der Veröffentlichung
02.03.2010Erstgutachter
Blum, NorbertZweitgutachter
Karpinski, MarekMetadaten
Zur Langanzeige
Zitierbare Links 
Inhalt
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.
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.
Schlagwörter
Graphentheorie, Matching, Algorithmus, Effizienz, Datenkomprimierung
Klassifikation (DDC)
004 InformatikLö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
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 = {https://hdl.handle.net/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 = {https://hdl.handle.net/20.500.11811/4528}
}
Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:
