Maximale Kreispackungen durch gute 3-Splits in Halin-Graphen

Otto, Christin

Maximale Kreispackungen durch gute 3-Splits in Halin-Graphen

dc.contributor.advisor	Recht, Peter
dc.contributor.author	Otto, Christin
dc.contributor.referee	Fischer, Anja
dc.date.accepted	2021-10-12
dc.date.accessioned	2021-11-25T09:13:23Z
dc.date.available	2021-11-25T09:13:23Z
dc.date.issued	2021
dc.description.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.	de
dc.identifier.uri	http://hdl.handle.net/2003/40576
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-22445
dc.language.iso	de	de
dc.subject	Maximale Kreispackungen	de
dc.subject	Kreispackungszahl	de
dc.subject	Halin-Graphen	de
dc.subject	Graphzerlegung	de
dc.subject.ddc	330
dc.subject.rswk	Graphentheorie	de
dc.subject.rswk	Kreis	de
dc.subject.rswk	Packung	de
dc.subject.rswk	Mathematik	de
dc.subject.rswk	Packungsproblem	de
dc.title	Maximale Kreispackungen durch gute 3-Splits in Halin-Graphen	de
dc.type	Text	de
dc.type.publicationtype	doctoralThesis	de
dcterms.accessRights	open access
eldorado.secondarypublication	false	de

Files

Original bundle

Now showing 1 - 1 of 1

Name:: Dissertation.pdf
Size:: 1.75 MB
Format:: Adobe Portable Document Format
Description:: DNB

Download

License bundle

Now showing 1 - 1 of 1

Name:: license.txt
Size:: 4.85 KB
Format:: Item-specific license agreed upon to submission
Description:

Download

Collections

Fachgebiet Operations Research und Wirtschaftsinformatik