Authors: Otto, Christin
Title: Maximale Kreispackungen durch gute 3-Splits in Halin-Graphen
Language (ISO): de
Abstract: In dieser Arbeit wird das Problem der Bestimmung einer maximalen kantendisjunkten Kreispackung bzw. der Bestimmung der Kreispackungszahl von Graphen untersucht. Die Bedeutung dieser theoretischen Problemstellung wird durch die Vorstellung dreier Anwendungen verdeutlicht. Da die Bestimmung solcher maximalen kantendisjunkten Kreispackungen sowie die Bestimmung der Kreispackungszahl NP-schwer sind, besteht die grundlegende Idee dieser Arbeit darin, Graphzerlegungen bestimmter Graphklassen zu nutzen und einen Bezug zwischen einer Kreispackung der Zerlegung und einer Kreispackung des Ursprungsgraphen herzustellen. Für serienparallele Graphen wird ein Linearzeitalgorithmus basierend auf einer SPQR-Zerlegung vorgestellt und evaluiert. Weiterhin wird eine Zerlegung für minimal 3-zusammenhängende Graphen vorgestellt, mit der verschiedene Ergebnisse für Halin-Graphen entwickelt werden. Unter anderem wird für spezielle Halin-Graphen gezeigt, dass die Bestimmung der Kreispackungszahl auf die Bestimmung der Kreispackungszahlen der Komponenten in der Zerlegung zurückgeführt werden kann.
Subject Headings: Maximale Kreispackungen
Kreispackungszahl
Halin-Graphen
Graphzerlegung
Subject Headings (RSWK): Graphentheorie
Kreis
Packung
Mathematik
Packungsproblem
URI: http://hdl.handle.net/2003/40576
http://dx.doi.org/10.17877/DE290R-22445
Issue Date: 2021
Appears in Collections:Fachgebiet Operations Research und Wirtschaftsinformatik

Files in This Item:
File Description SizeFormat 
Dissertation.pdfDNB1.79 MBAdobe PDFView/Open


This item is protected by original copyright



Items in Eldorado are protected by copyright, with all rights reserved, unless otherwise indicated.