Benutzer: Gast  Login
Originaltitel:
On the Minimum Bisection Problem in Tree-Like and Planar Graphs 
Originaluntertitel:
Structural and Algorithmic Results 
Übersetzter Titel:
Über das Minimum Bisection Problem in baumartigen und planaren Graphen 
Übersetzter Untertitel:
Strukturelle und algorithmische Resultate 
Jahr:
2017 
Dokumenttyp:
Dissertation 
Institution:
Fakultät für Mathematik 
Betreuer:
Gritzmann, Peter (Prof. Dr.) 
Gutachter:
Gritzmann, Peter (Prof. Dr.); Taraz, Anusch (Prof. Dr.); Fernandez, Christina G. (Prof., Ph.D.) 
Sprache:
en 
Fachgebiet:
MAT Mathematik 
Stichworte:
graph theory, minimum bisection 
Übersetzte Stichworte:
Graphentheorie, Minimum Bisection 
TU-Systematik:
MAT 500d; MAT 910d 
Kurzfassung:
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. 
Übersetzte Kurzfassung:
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. 
Mündliche Prüfung:
10.05.2017 
Dateigröße:
3089975 bytes 
Seiten:
258 
Letzte Änderung:
14.08.2017