Universität zu Köln

Structure Analysis of Some Generalizations of Matchings and Matroids under Algorithmic Aspects of Matchings and Matroids Under Algorithmic Aspects

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.

[img]
Preview
PDF
Download (895Kb) | Preview

    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 abstract:
    AbstractLanguage
    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:
    CreatorsEmail
    Peis, Brittabpeis@math.uni-dortmund.de
    URN: urn:nbn:de:hbz:38-21133
    Subjects: Mathematics
    Uncontrolled Keywords:
    KeywordsLanguage
    Matroide , distributive Verbände , König-Egervary Graph, Greedy AlgorithmusGerman
    Matroids , distributive lattices, König-Egervary graph , vertex cover , greedy algorithmEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Mathematisches Institut
    Language: English
    Date: 2007
    Date Type: Completion
    Date of oral exam: 29 November 2006
    Full Text Status: Public
    Date Deposited: 05 Sep 2007 09:08:25
    Referee
    NameAcademic Title
    Faigle, UlrichProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/2113

    Actions (login required)

    View Item