Matchings in balanced hypergraphs

Scheidweiler, Robert Berthold; Triesch, Eberhard

doi:3645

Matchings in balanced hypergraphs = Matchings in balancierten Hypergraphen

Scheidweiler, Robert Berthold (Author)

2011

Verantwortlichkeitsangabevorgelegt von Robert Berthold Scheidweiler

ImpressumAachen : Publikationsserver der RWTH Aachen University 2011

Umfang73 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2011

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2011-04-19

Online
URN: urn:nbn:de:hbz:82-opus-36450
URL: https://publications.rwth-aachen.de/record/64351/files/3645.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Matching <Graphentheorie> (Genormte SW) ; Knotenüberdeckungsproblem (Genormte SW) ; Hypergraph (Genormte SW) ; Mathematik (frei) ; matching (frei) ; vertex cover (frei) ; balanced hypergraph (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Die vorliegende Arbeit behandelt das Matching und Vertex Cover Problem in balancierten Hypergraphen. Diese stellen eine Verallgemeinerung von bipartiten Graphen dar und sind von Berge in den 70er Jahren definiert worden. Im ersten Kapitel werden die grundlegenden Begriffe definiert. Das nächste Kapitel behandelt die Klasse der balancierten Hypergraphen. Zunächst wird das Matching Problem in zwei speziellen Unterklassen untersucht und einige Färbungseigenschaften von balancierten Hypergraphen werden angegeben. Danach wird der Zusammenhang von Matchingzahlen und Regularität betrachtet und im Anschluss ein neuer Beweis für den Satz von König angegeben. Weitere Dualitätseigenschaften, die als kombinatorische Formulierung der Complementary Slackness Relation interpretiert werden können, werden danach erarbeitet. Zum Ende des zweiten Kapitels werden die zugehörigen Polyeder untersucht und erklärt wie die Ideen aus Kapitel zwei algorithmisch zum Vergrößern von Matchings benutzt werden können. Das dritte Kapitel befasst sich mit den Hauptresultaten dieser Arbeit - mehreren Zerlegungen von balancierten Hypergraphen, die eine Verallgemeinerung der klassischen Gallai Edmonds Zerlegung für Graphen darstellen. Basierend auf diesen Zerlegungen wird im vierten Kapitel ein neuer Beweis für den Satz von Hall in balancierten Hypergraphen angegeben. Das fünfte Kapitel beinhaltet weitere Anwendungen der vorangegangen Kapitel, z.B. neue Charakterisierungen für balancierte Hypergraphen und die Untersuchung von einigen interessanten Unterklassen.

The present work deals with the matching and vertex cover problem in balanced hypergraphs. This class of hypergraphs is, according to the definition by Berge in the 70s, one possible generalization of bipartite graphs. In the first chapter we define basic notions about graphs and hypergraphs. The next chapter deals with the class of balanced hypergraphs. At first we state some known coloring properties of balanced hypergraphs and investigate the matching problem in two important subclasses. Then we analyse the connection between regularity and maximum matchings. After that we give a new proof of König's Theorem for balanced hypergraphs and discuss further duality properties between matchings and vertex covers and give several new results, which can be interpreted as combinatorial formulations and strengthenings of the complementary slackness relation. In the following we investigate the associated polyhedra and outline how our ideas can be used to augment matchings algorithmically. The third chapter deals with the main results of this work - a new decomposition theory for balanced hypergraphs. We generalize the classical Gallai Edmonds decomposition of graphs to balanced hypergraphs in several different ways. Based on these decompositions we give a new, short, and combinatorial proof of Hall's theorem in balanced hypergraphs in chapter four. In the last chapter we show several applications of our theory, e.g., we give several new characterizations of balanced hypergraphs, characterize 1-extendability, and investigate several interesting subclasses.

Fulltext:
PDF