http://www.tu-ilmenau.de

Logo TU Ilmenau


Arbeitsgruppe
Diskrete Mathematik und Algebra


Ansprechpartner

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

Fachgebietsleiter

Telefon +49 3677 69-3633

E-Mail senden


Ihre Position

INHALTE

Publikationsliste seit 1990

Anzahl der Treffer: 361
Erstellt: Sun, 22 Oct 2017 06:41:26 +0200 in 0.0324 sec


Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Schiermeyer, Ingo; Sprengel, Eva-Maria
Packing disjoint cycles over vertex cuts. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 13/14, S. 1974-1978
http://dx.doi.org/10.1016/j.disc.2010.03.009
Draque Penso, Lucia; Rautenbach, Dieter; Szwarcfiter, Jayme Luiz
Cycles, paths, connectivity and diameter in distance graphs. - In: Graph theoretic concepts in computer science : 35th international workshop, WG 2009, Montpellier, France, June 24 - 26, 2009 ; revised papers. - Berlin [u.a.] : Springer / WG ; 35 (Montpellier) : 2009.06.24-26., ISBN 978-3-642-11409-0, (2010), S. 320-328

http://dx.doi.org/10.1007/978-3-642-11409-0
Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter; Szwarcfiter, Jayme L.
Some remarks on the geodetic number of a graph. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 4, S. 832-837
http://dx.doi.org/10.1016/j.disc.2009.09.018
Scheide, Diego
Graph edge colouring: Tashkinov trees and Goldberg's conjecture. - In: Journal of combinatorial theory / B. - Orlando, Fla : Academic Press, Bd. 100 (2010), 1, S. 68-96
http://dx.doi.org/10.1016/j.jctb.2009.04.001
Brandt, Stephan; Budajová, Kristína; Rautenbach, Dieter; Stiebitz, Michael
Edge colouring by total labellings. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 2, S. 199-205
http://dx.doi.org/10.1016/j.disc.2008.09.013
Brandt, Stephan
Triangle-free graphs whose independence number equals the degree. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 3, S. 662-669
http://dx.doi.org/10.1016/j.disc.2009.05.021
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter
An independent dominating set in the complement of a minimum dominating set of a tree. - In: Applied mathematics letters. - Amsterdam [u.a.] : Elsevier Sci, Bd. 23 (2010), 1, S. 79-81
http://dx.doi.org/10.1016/j.aml.2009.08.008
Král', Daniel; Sereni, Jean-Sébastien; Stiebitz, Michael
A new lower bound on the number of perfect matchings in cubic graphs. - In: SIAM journal on discrete mathematics. - Philadelphia, Pa : Soc, ISSN 10957146, Bd. 23 (2009), 3, S. 1465-1483
http://dx.doi.org/10.1137/080723843
Artmann, Sarah; Pruchnewski, Anja
Constructing a dominating set for bipartite graphs in several rounds. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 7 S., 167,9 KB). - (Preprint. - M09,37)
http://www.db-thueringen.de/servlets/DocumentServlet?id=14792
Scheide, Diego
Edge colourings of multigraphs. - 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