On the Minimum Bisection Problem in Tree-Like and Planar Graphs: Structural and Algorithmic Results

Schmidt, Tina Janne

Tina Janne Schmidt

If you experience problems opening the document, please try this link.

Original title:: On the Minimum Bisection Problem in Tree-Like and Planar Graphs
Original subtitle:: Structural and Algorithmic Results
Translated title:: Über das Minimum Bisection Problem in baumartigen und planaren Graphen
Translated subtitle:: Strukturelle und algorithmische Resultate
Author:: Schmidt, Tina Janne
Year:: 2017
Document type:: Dissertation
Faculty/School:: Fakultät für Mathematik
Advisor:: Gritzmann, Peter (Prof. Dr.)
Referee:: Gritzmann, Peter (Prof. Dr.); Taraz, Anusch (Prof. Dr.); Fernandez, Christina G. (Prof., Ph.D.)
Language:: en
Subject group:: MAT Mathematik
Keywords:: graph theory, minimum bisection
Translated keywords:: Graphentheorie, Minimum Bisection
TUM classification:: MAT 500d; MAT 910d
Abstract:: Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two classes of equal size while minimizing the number of edges between these classes. This thesis investigates the structure of bounded-degree trees and planar graphs with large minimum bisection width. For tree-like and planar graphs, linear-time algorithms computing bisections within certain bounds are presented. Moreover, the results are generalized to Minimum k-Section.
Translated abstract:: Minimum Bisection bezeichnet das NP-schwere Problem, die Knoten eines Graphen in zwei gleich große Klassen aufzuteilen, sodass die Anzahl der Kanten dazwischen minimiert wird. Hier wird die Struktur von Grad-beschränkten Bäumen und planaren Graphen mit großer Bisektionsweite untersucht. Linearzeit-Algorithmen, die für baumartige und planare Graphen Bisektionen innerhalb bestimmter Schranken berechnen, werden vorgestellt. Außerdem werden die Resultate auf Minimum k-Section verallgemeinert.
WWW:: https://mediatum.ub.tum.de/?id=1338548
Date of submission:: 27.12.2016
Oral examination:: 10.05.2017
File size:: 3089975 bytes
Pages:: 258
Urn (citeable URL):: https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20170510-1338548-1-2
Last change:: 14.08.2017
BibTeX