Benutzer: Gast  Login
Wenn Sie Schwierigkeiten haben, das Dokument zu öffnen, versuchen Sie auch bitte diesen Link
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
Autor:
Schmidt, Tina Janne
Jahr:
2017
Dokumenttyp:
Dissertation
Fakultät/School:
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.
WWW:
https://mediatum.ub.tum.de/?id=1338548
Eingereicht am:
27.12.2016
Mündliche Prüfung:
10.05.2017
Dateigröße:
3089975 bytes
Seiten:
258
Urn (Zitierfähige URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20170510-1338548-1-2
Letzte Änderung:
14.08.2017
 BibTeX