Graph-Einbettungen
unter besonderer Ber¨ucksichtigung von
Gitternetzwerken
Dissertation
von
Ulf-Peter Schroeder
Schriftliche Arbeit zur Erlangung des Grades
eines Doktors der Naturwissenschaften
Fachbereich Mathematik/Informatik
Universit¨at Paderborn
Paderborn,
Dezember 2000
Danksagung
Die vorliegende Arbeit entstand w¨ahrend meiner T¨atigkeit als wissenschaftlicher Mitarbeiter im
Fachbereich Mathematik/Informatik an der Universit¨at Paderborn. Ich m¨ochte mich an dieser
Stelle bei all jenen bedanken, die zum Gelingen dieser Arbeit beigetragen haben.
Mein besonderer Dank gilt Prof. Dr. Burkhard Monien f¨ur die Betreuung dieser Arbeit. Die
T¨atigkeit an seinem Lehrstuhl erm¨oglichte mir einen tiefgehenden und breiten Einblick in ak-
tuelle Forschungsthemen. Dar¨uber hinaus sorgte er sowohl durch die technische und finanzielle
Ausstattung, als auch durch das Schaffen einer stimulierenden Arbeitsatmosph¨are mit entspre-
chenden wissenschaftlichen Diskussionen f¨ur das Gelingen meiner Arbeit.
F¨ur die vorbildliche wissenschaftliche Zusammenarbeit m¨ochte ich mich des weiteren bei
meinen Kollegen Dr. habil. Sergei Bezrukov und Dr. Markus R¨ottger bedanken. Viele der in die-
ser Arbeit dargestellten Ergebnisse sind durch einen intensiven Ideenaustausch mit den vorge-
nannten Personen entstanden oder durch deren konstruktive Kritik erheblich verbessert worden.
Bei Christian Voss und Dr. MarkusR¨ottger m¨ochte ich mich zus¨atzlich f¨ur das Korrekturlesen
dieser Arbeit bedanken, wodurch einige Fehler aufgedeckt werden konnten und die Lesbarkeit
vieler Beweise deutlich verbessert werden konnte.
Weiterer Dankgiltmeinen KollegenRobert Els¨asser,Dr. Ralf Diekmann,Robert Preis, J¨urgen
Schulze und Dr. Walter Unger f¨ur Anregungen, Hilfestellungen und fruchtbaren Diskussionen.
Schließlich m¨ochte ich mich bei meinen Eltern bedanken, die mich immer unterst¨utzten und
meine Ausbildung erm¨oglichten.
Paderborn, im Dezember 2000 Ulf-Peter Schroeder
i
ii
Inhaltsverzeichnis
1 Einleitung 1
1.1 Das Graph-Einbettungsproblem .......................... 3
1.2 Das Graph-Partitionierungsproblem . . . . . ................... 7
1.3 Resultate und Gliederung der Arbeit . . . . . ................... 9
2 Definitionen und Hilfss¨
atze 11
3 Untere-Schranken-Methoden f¨ur einige Kostenmaße von Einbettungen 19
3.1 Isoperimetrische Probleme auf Graphen . . . ................... 19
3.2 Untere-Schranken-Methoden f¨ur die Kantenstreckung ............... 26
3.3 Untere-Schranken-Methoden f¨ur die Kantenauslastung . . . . . . ........ 28
3.4 Untere-Schranken-Methoden f¨ur den minimalen Schnitt einer k-Partitionierung . 29
4 Einbettungen bin¨
arer Hypercubes in d-dimensionale Gitter 33
4.1 Stand der Forschung . . . . . . .......................... 33
4.2 ¨
Uberblick ¨uber die erzielten Ergebnisse . . . ................... 37
4.3 Betrachtung der Kantenauslastung . . . . . . ................... 38
4.3.1 Die Schnittweite von Qn.......................... 38
4.3.2 Das Kantenauslastungsproblem . . . ................... 43
4.3.3 Nachbetrachtungen . . . .......................... 46
4.4 Betrachtung der Kantenstreckung .......................... 47
4.4.1 Das Kantenstreckungsproblem f¨ur zweidimensionale Gitter . . . . . . . 47
4.4.2 Eine asymptotische obere Schranke f¨ur die Kantenstreckung . . . . . . . 51
4.4.3 Eine asymptotische untere Schranken f¨ur die Kantenstreckung . . . . . . 55
4.5 Betrachtung der Leitungsl¨ange . .......................... 62
4.6 Betrachtung uniaxialer Algorithmen . . . . . ................... 65
4.7 Zusammenfassung ................................. 73
iii
Loading more pages...