http://www.tu-ilmenau.de

Logo TU Ilmenau



Foto des Ansprechpartners
Ansprechpartner

Prof. Dr. rer. nat. habil. Matthias Kriesell

Institutsdirektor

Telefon +49 3677 69-3633

E-Mail senden


Ihre Position

INHALTE

Veröffentlichungen

Veröffentlichungen am Institut für Mathematik seit 1990

Anzahl der Treffer: 1176
Erstellt: Mon, 24 Feb 2020 23:05:44 +0100 in 0.0415 sec


Scheide, Diego;
Edge colourings of multigraphs, 2009. - Online-Ressource (PDF-Datei: 112 S., 2666 KB). Ilmenau : Techn. Univ., Diss., 2009

Das Kantenfärbungsproblem besteht darin, den chromatischen Index eines (Multi-)Graphen G zu ermitteln, d.h. die minimale Anzahl an Farben, mit denen man die Kanten von G so färben kann, dass keine zwei benachbarten Kanten die gleiche Farbe erhalten. Kantenfärbungsprobleme treten in verschiedenen Scheduling-Anwendungen auf, typischerweise in Verbindung mit Task-Processing oder Netzwerk-Kommunikation. Da das Kantenfärbungsproblem NP-schwer ist, sind gute Approximationsalgorithmen gefordert. In dieser Dissertation werden verschiedene Färbungstechniken erweitert und neue Färbungsalgorithmen entworfen. Ausgehend von einem klassischen Resultat von Vizing, wird ein neuer Graphenparameter - die Fächerzahl - vorgestellt. Dies führt zu einem Färbungsalgorithmus, der durch eine spezielle Kantensortierung Vizings Fächer in bestmöglicher Weise nutzen kann. Eines der größten bisher ungelösten Probleme auf dem Gebiet der Kantenfärbungen ist Goldbergs Vermutung. Goldberg (und unabhängig davon auch Andersen und Seymour) vermutete eine obere Schranke für den chromatischen Index chi', die vom Maximalgrad Delta und einer maximalen Dichte w abhängt, und zwar chi'<=max{Delta+1,w}. Da Delta und w beides untere Schranken für chi' sind, hat Goldbergs Schranke somit eine absolute Abweichung von höchstens 1 vom Optimum. In dieser Dissertation werden einige neue obere Schranken für chi' entwickelt, die die Lücke zwischen den bereits bekannten Schranken und Goldbergs vermuteter Schranke verkleinert. Die beiden wichtigsten neuen Schranken sind max{Delta+1+(Delta-2)/14,w} und max{Delta+sqrt((Delta-1)/2),w}. Die Laufzeiten der zugehörigen Färbungsalgorithmen sind polynomiell beschränkt bzgl. der Eckenzahl und der Kantenzahl des zu färbenden Graphen. Da aber ein Graph einfach durch Angabe der Ecken und Kantenvielfachheiten beschrieben werden kann, sind die genannten Algorithmen somit keine echten Polynomialzeitalgorithmen. Im letzten Kapitel der Dissertation wird allerdings gezeigt, wie sich durch alternative Datenstrukturen und ein ivide-and-Conquer-Verfahren diese Algorithmen auch als Polynomialzeitalgorithmen implementieren lassen.



http://www.db-thueringen.de/servlets/DocumentServlet?id=13785
Neundorf, Werner;
Fourier-Reihen, [Pi] und Cotangens. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: [47] S., 2,36 MB). . - (Preprint. - M09,36)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14544
Rautenbach, Dieter; Schäfer, Philipp Matthias
Null-homotopic graphs and triangle-completions of spanning trees. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 4 S., 144,3 KB). . - (Preprint. - M09,35)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14440
Rautenbach, Dieter; Schäfer, Philipp Matthias
Finite sholander trees, trees, and their betweennesses. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 8 S., 204,6 KB). . - (Preprint. - M09,34)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14439
Rautenbach, Dieter; Schäfer, Philipp Matthias
Strict betweennesses induced by posets as well as by graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 8 S., 185,9 KB). . - (Preprint. - M09,33)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14426
Löwenstein, Christian; Pedersen, Anders Sune; Rautenbach, Dieter; Regen, Friedrich
Independence, odd girth, and average degree. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 15 S., 232,7 KB). . - (Preprint. - M09,32)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14425
Harant, Jochen; Rautenbach, Dieter
Independence in connected graphs. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 10 S., 193,9 KB). . - (Preprint. - M09,31)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14424
Azizov, Tomas Ya.; Trunk, Carsten
On domains of PT symmetric operators related to -y"(x) + (-1) n x 2n y(x). - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 15 S., 186,1 KB). . - (Preprint. - M09,30)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14408
Steigenberger, Joachim; Abeßer, Harald
Quasistatic inflation processes within compliant tubes. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 30 S., 326,7 KB). . - (Preprint. - M09,29)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14407
Abeßer, Harald; Steigenberger, Joachim
Ein Optimalsteuerproblem mit einem speziellen Zielfunktional und Zustandsbeschränkungen in einem Teilintervall bei beliebigem Relativgrad. - Ilmenau : Techn. Univ., Inst. für Mathematik, 2009. - Online-Ressource (PDF-Datei: 21 S., 667,4 KB). . - (Preprint. - M09,28)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14422