Algorithmen für Matchingprobleme in speziellen Graphklassen
Algorithmen für Matchingprobleme in speziellen Graphklassen
View/Type of Scholarly Publication
DissertationDate of Exam
03.02.2010Date of Publication
02.03.2010Advisor
Blum, NorbertCo-Referee
Karpinski, MarekMetadata
Show full item record
Citable Links 
Abstract
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.
Subjects
Graphentheorie, Matching, Algorithmus, Effizienz, Datenkomprimierung
Classification (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}
}
The following license files are associated with this item:
