User: Guest  Login
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 
Year:
2017 
Document type:
Dissertation 
Institution:
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. 
Oral examination:
10.05.2017 
File size:
3089975 bytes 
Pages:
258 
Last change:
14.08.2017