Maximum Cycle Packing – Obere Schranken an Kreispackungszahlen in polyhedralen Graphen
Creators: name: Stehling, Stefan
Publisher: name: TU Dortmund
Year: 2021
Subjects: subject: Maximum cycle packing
subject: Polyhedral graphs
subject: 330

description: In vielen Bereichen des Operations Research sind graphentheoretische Konzepte und Kennzahlen bei der Modellierung von Optimierungsproblemen von grundlegender Bedeutung. Zwei in dieser Arbeit speziell behandelte Kennzahlen sind durch die sog. knoten- bzw. kantendisjunkte Kreispackungszahlen eines Graphen gegeben. Anwendungsbeispiele, die die praktische Relevanz der Kreispackungszahlen bzw. der maximalen Kreispackungen zeigen, bilden u.a. das Genom Rearrangement in der Biologie, die Ausgestaltung optischer Netzwerke oder die Rundgangsplanung. Im Allgemeinen ist die Bestimmung einer maximalen Kreispackung sowie der zugehörigen Kreispackungszahl ein NP-schweres Problem. Demnach werden Heuristiken zur Annäherung der Kennzahlen herangezogen bzw. spezielle Struktureigenschaften der betrachteten Graphen gefordert, um exakte Resultate für bzw. gute Schranken an die Kreispackungszahlen anzugeben. Genau hier setzt diese Arbeit an und es werden für speziell gewählte polyhedrale Graphen sowie zwei Unterklassen polyhedraler Graphen mit der Klasse der Halin-Graphen und den Fulleren-Graphen bestmögliche obere Schranken an die betrachtete Unterklasse angegeben. Zudem wird jeweils eine Konstruktionssystematik von Graphen vorgestellt, derart, dass auch eine maximale Kreispackung innerhalb der gewählten Graphen angegeben werden kann. Es gelang für polyhedrale Graphen mit fester Ordnung und Größe, obere Schranken an Kreispackungszahlen anzugeben. Zudem wurde für Halin-Graphen und Fulleren-Graphen bewiesen, dass die kantendisjunkte Kreispackungszahl gleich der Unabhängigkeitszahl des zugehörigen Dualgraphen ist. Für Fulleren-Graphen konnte eine in der Ordnung nicht monoton wachsende bestmögliche obere Schranke an die kantendisjunkte Kreispackungszahl abgeleitet werden.
description: In many areas of operations research, graph-theoretical concepts and characteristics are of fundamental importance when modeling optimization problems. Two figures treated in this work are given by the so-called vertex- or edge-disjoint circle packing numbers of a graph. Application examples showing the practical relevance of the number of cycles packings or maximum cycle packings include genome rearrangement in biology, the design of optical networks or tour planning. In general, the determination of a maximum cycle packing as well as the associated number of cycle packing is a problem that is NP complete. Accordingly, heuristics are used to approximate these figures or special structural properties of the graphs under consideration are required in order to give exact results for or good bounds on the cycle packing numbers. This is exactly where this work focuses upon. For selected polyhedral graphs as well as two subclasses of polyhedral graphs, which are the class of Halin graphs and the fullerene graphs, a best possible upper bounds on the considered subclass are derived. In addition, a construction system for graphs is presented in such a way that a maximum cycle packing can also be specified within the selected graph. For polyhedral graphs with a fixed order and size, it was possible to specify upper bounds on cycle packing numbers. In addition, it was proven for Halin graphs and fullerene graphs that the edge-disjoint cycle packing number is equal to the independence number of the dual graph. For fullerene graphs, a best possible upper bound which does not increase monotonically in the order of the given graph, could be derived for the edge-disjoint cycle packing number.