Universität zu Köln

Peis, Britta (2007). Structure Analysis of Some Generalizations of Matchings and Matroids under Algorithmic Aspects of Matchings and Matroids Under Algorithmic Aspects. PhD thesis, Universität zu Köln.

Preview

PDF MeineDiss.pdf Download (916kB)

Abstract

Combinatorial optimization problems whose underlying structures are matchings or matroids are well-known to be solvable with efficient algorithms. Matroids can even be characterized by a simple greedy algorithm. In the first part of this thesis, some generalizations of matroids which allow the ground set to be partially ordered are considered. In particular, it will be shown that a special type of lattice polyhedra, for which Dietrich and Hoffman recently established a dual greedy algorithm, can be reduced to ordinary polymatroids. Moreover, strong exchange structures, Gauss greedoids and Delta-matroids will be extended from Boolean lattices to general distributive lattices, and the resulting structures will be characterized by certain greedy-type algorithms. While a matching of maximal size can be determined by a polynomial algorithm, the dual problem of finding a vertex cover of minimal size in general graphs is one of the hardest problems in combinatorial optimization. However, in case the graph belongs to the class of K\"onig-Egerv\'ary graphs, a maximum matching can be used to construct a minimum vertex cover. Lovasz and Korach characterized König-Egervary graphs by the exclusion of forbidden subgraphs. In the second part of this dissertation, the structure of König-Egervary graphs and the more general Red/Blue-split graphs will be analyzed. Red/Blue-split graphs have red and blue colored edges and the vertices of which can be split into two stable sets with respect to the red and blue edges, respectively. An algorithm that either determines a feasible partition of the vertices, or returns a red-blue colored subgraph (called ``flower'') characterizing non-Red/Blue-split graphs will be presented. This characterization allows the deduction of Lovasz and Korach's characterizations of König-Egerv\'ary graphs in case the red edges of the flower form a maximum matching. Furthermore, weighted Red/Blue-split graphs which model integrally solvable simple systems are introduced. A simple system is an inequality system where the sum of absolute values in each row of the integral matrix does not exceed the value two. A shortest-path algorithm and the presented Red/Blue-split algorithm will be used to find an integral solution of a simple system. These two algorithms lead to a characterization of weighted Red/Blue-split graphs by forbidden weighted subgraphs.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Strukturanalyse einiger Verallgemeinerungen von Matchings und Matroiden unter algorithmischen Aspekten German
Translated abstract:	Abstract Language Es ist seit langem bekannt, dass Kombinatorische Optimierungsprobleme, denen Matroid- oder Matchingstrukturen zugrunde liegen, mit effizienten Algorithmen lösbar sind. Matroide können sogar durch einen einfachen Greedyalgorithmus charakterisiert werden. Im ersten Teil dieser Arbeit werden Verallgemeinerungen von Matroiden behandelt, die eine Halbordung der Grundmenge zulassen. Es wird bewiesen, dass eine bestimmte Klasse von Verbandspolyedern, für die Hoffman und Dietrich kürzlich die Optimalität eines dualen Greedyalgorithmus bewiesen haben, letztendlich auf Polymatroide zurückgeführt werden können. Desweiteren werden Starke Austauschstrukturen, Gauss Greedoide und Delta-Matroide vom Bool'schen Verband zu allgemeinen distributiven Verbänden verallgemeinert, und die so entstehenden Strukturen durch greedy-artige Algorithmen charakterisiert. Während ein Matching maximaler Größe in polynomieller Zeit bestimmt werden kann, ist das duale Problem der Bestimmung einer minimalen Knotenüberdeckung in allgemeinen Graphen NP-schwer. Gehört der Graph allerdings zur Klasse der König-Egervary Graphen, kann eine minimale Knotenüberdeckung mit Hilfe eines maximalen Matchings konstruiert werden. Lovasz und Korach haben König-Egervary Graphen durch Ausschluß verbotener Untergraphen charakterisiert. Im zweiten Teil der Dissertation wird die Struktur der König-Egervary Graphen und der allgemeineren Rot/Blau-Split Graphen analysiert. Rot/Blau-Split Graphen besitzen rot und blau gefärbte Kanten und lassen eine Aufteilung der Knotenmenge in eine stabile Menge bezüglich der roten Kanten und eine stabile Menge bezüglich der blauen Kanten zu. Es wird ein Algorithmus vorgestellt, der die Knoten entweder in zwei zulässige Mengen aufteilt, oder einen rot-blauen Untergraphen (genannt "Flower") bestimmt, der beweist, dass der Graph kein Rot/Blau-Split Graph ist. Betrachtet man den Spezialfall, bei dem die roten Kanten ein maximales Matching bilden, führt diese Charakterisierung direkt zu den verbotenen Untergraphen, mit denen Lovasz und Korach König-Egervary Graphen charakterisierten. Zusätzlich werden gewichtete Rot/Blau-Split Graphen vorgestellt, die ganzzahlig lösbare "einfache" Ungleichungssysteme modellieren. Dabei wird ein System von Ungleichungen einfach genannt, wenn die Matrix ganzzahlig ist und die Eigenschaft besitzt, dass in jeder Reihe die Summe der Absolutbeträge kleiner gleich zwei ist. Mit Hilfe eines Kürzeste-Wege Algorithmus und des vorgestellten Rot/Blau-Split Algorithmus wird eine ganzzahlige Lösung eines einfachen Ungleichungssystems bestimmt, sofern sie existiert. Diese beiden Algorithmen führen zu einer Charakterisierung gewichteter Rot/Blau-Split Graphen, bzw. ganzzahlig lösbarer einfacher Ungleichungssysteme, durch verbotene gewichtete Untergraphen. German
Creators:	Creators Email ORCID ORCID Put Code Peis, Britta bpeis@math.uni-dortmund.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-21133
Date:	2007
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Mathematical Institute
Subjects:	Mathematics
Uncontrolled Keywords:	Keywords Language Matroide , distributive Verbände , König-Egervary Graph, Greedy Algorithmus German Matroids , distributive lattices, König-Egervary graph , vertex cover , greedy algorithm English
Date of oral exam:	29 November 2006
Referee:	Name Academic Title Faigle, Ulrich Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/2113