Cut Problems on Graphs

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.48693/154
Open Access logo originally created by the Public Library of Science (PLoS)
Titel: Cut Problems on Graphs
Autor(en): Nover, Alexander
Erstgutachter: Prof. Dr. Martina Juhnke-Kubitzke
Zweitgutachter: Prof. Dr. Markus Chimani
Prof. Dr. Volker Kaibel
Zusammenfassung: Cut problems on graphs are a well-known and intensively studied class of optimization problems. In this thesis, we study the maximum cut problem, the maximum bond problem, and the minimum multicut problem through their associated polyhedra, i.e., the cut polytope, the bond polytope, and the multicut dominant, respectively. Continuing the research on the maximum cut problem and the cut polytope, we present a linear description for cut polytopes of K_{3,3}-minor-free graphs as well as an algorithm solving the maximum cut problem on these graphs in the same running time as planar maximum cut. Moreover, we give a complete characterization of simple and simplicial cut polytopes. Considering the maximum cut problem from an algorithmic point of view, we propose an FPT-algorithm for the maximum cut problem parameterized by the crossing number. We start the structural study of the bond polytope by investigating its basic properties and the effect of graph operations on the bond polytope and its facet-defining inequalities. After presenting a linear-time reduction of the maximum bond problem to the maximum bond problem on 3-connected graphs, we discuss valid and facet defining inequalities arising from edges and cycles. These inequalities yield a complete linear description for bond polytopes of 3-connected planar (K_5-e)-minor-free graphs. This polytopal result is mirrored algorithmically by proposing a linear-time algorithm for the maximum bond problem on (K_5-e)-minor-free graphs. Finally, we start the structural study of the multicut dominant. We investigate basic properties, which gives rise to lifting and projection results for the multicut dominant. Then, we study the effect of graph operations on the multicut dominant and its facet-defining inequalities. Moreover, we present facet-defining inequalities supported on stars, trees, and cycles as well as separation algorithms for the former two classes of inequalities.
URL: https://doi.org/10.48693/154
https://osnadocs.ub.uni-osnabrueck.de/handle/ds-202207187220
Schlagworte: maximum cut; maximum bond; minimum multicut; discrete geometry; combinatorial optimization
Erscheinungsdatum: 18-Jul-2022
Lizenzbezeichnung: Attribution 3.0 Germany
URL der Lizenz: http://creativecommons.org/licenses/by/3.0/de/
Publikationstyp: Dissertation oder Habilitation [doctoralThesis]
Enthalten in den Sammlungen:FB06 - E-Dissertationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis_nover.pdfPräsentationsformat1,04 MBAdobe PDF
thesis_nover.pdf
Miniaturbild
Öffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons