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.
| Identifer | oai:union.ndltd.org:uni-osnabrueck.de/oai:osnadocs.ub.uni-osnabrueck.de:ds-202207187220 |
| Date | 18 July 2022 |
| Creators | Nover, Alexander |
| Contributors | Prof. Dr. Martina Juhnke-Kubitzke, Prof. Dr. Markus Chimani, Prof. Dr. Volker Kaibel |
| Source Sets | Universität Osnabrück |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis |
| Format | application/pdf, application/zip |
| Rights | Attribution 3.0 Germany, http://creativecommons.org/licenses/by/3.0/de/ |
Page generated in 0.0019 seconds