Matching minors in bipartite graphs

dc.contributor.advisorKreutzer, Stephan
dc.contributor.authorWiederrecht, Sebastian
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeKreutzer, Stephan
dc.contributor.refereeDiestel, Reinhard
dc.contributor.refereeSergey, Norin
dc.date.accepted2021-05-07
dc.date.accessioned2022-04-19T13:26:05Z
dc.date.available2022-04-19T13:26:05Z
dc.date.issued2022
dc.descriptionPublished in print by Universitätsverlag der TU Berlin, ISBN 978-3-7983-3252-2 (ISSN 2199-5249)en
dc.description.abstractIn this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of a cross over a conformal cycle by means of a topological property. Furthermore, we develope a theory for perfect matching width, a width parameter for graphs with perfect matchings introduced by Norin. here we show that the disjoint alternating paths problem can be solved in polynomial time on graphs of bounded width. Moreover, we show that every bipartite graph with high perfect matching width must contain a large grid as a matching minor. Finally, we prove an analogue of the we known Flat Wall theorem and provide a qualitative description of all bipartite graphs which exclude a fixed matching minor.en
dc.description.abstractIn der vorliegenden Arbeit werden fundamentale Teile des Graphminorenprojekts von Robertson und Seymour für das Studium von Matching Minoren adaptiert und Verbindungen zur Strukturtheorie gerichteter Graphen aufgezeigt. Wir entwickeln matchingtheoretische Analogien zu etablierten Resultaten des Graphminorenprojekts: Wir charakterisieren die Existenz eines Kreuzes über einem konformen Kreis mittels topologischer Eigenschaften. Weiter entwickeln wir eine Theorie zu perfekter Matchingweite, einem Weiteparameter für Graphen mit perfekten Matchings, der von Norin eingeführt wurde. Hier zeigen wir, dass das Disjunkte Alternierende Pfade Problem auf bipartiten Graphen mit beschränkter Weite in Polynomialzeit lösbar ist. Weiter zeigen wir, dass jeder bipartite Graph mit hoher perfekter Matchingweite ein großes Gitter als Matchingminor enthalten muss. Schließlich zeigen wir ein Analogon des bekannten Flat Wall Theorem und geben eine qualitative Beschreibung aller bipartiter Graphen an, die einen festen Matching Minor ausschließen.de
dc.identifier.eissn2199-5257
dc.identifier.isbn978-3-7983-3253-9
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/16184
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14958
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc004 Datenverarbeitung; Informatikde
dc.subject.ddc510 Mathematikde
dc.subject.othermatching minoren
dc.subject.otherstructural graph theoryen
dc.subject.otherbipartiteen
dc.subject.otherperfect matchingen
dc.subject.otherMatching Minorde
dc.subject.otherstrukturelle Graphentheoriede
dc.subject.otherBipartitde
dc.subject.otherperfektes Matchingde
dc.titleMatching minors in bipartite graphsen
dc.title.translatedMatching Minoren in bipartiten Graphende
dc.typeDoctoral Thesisen
dc.type.versionpublishedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Logik und Semantikde
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.groupFG Logik und Semantikde
tub.affiliation.instituteInst. Softwaretechnik und Theoretische Informatikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber16en
tub.series.nameFoundations of computingen
Files
Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
wiederrecht_sebastian.pdf
Size:
5.84 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
license.txt
Size:
4.86 KB
Format:
Item-specific license agreed upon to submission
Description:
Collections