Publikationen

Anzahl der Treffer: 142
Erstellt: Wed, 27 Mar 2024 23:22:28 +0100 in 0.0789 sec


Kostochka, Alexandr V.; Stiebitz, Michael; Woodall, Douglas R.
Ohba's conjecture for graphs with independence number five. - In: Discrete mathematics, Bd. 311 (2011), 12, S. 996-1005

http://dx.doi.org/10.1016/j.disc.2011.02.026
Brandt, Stephan; Miškuf, Jozef; Rautenbach, Dieter; Regen, Friedrich; Ruzsa, Imre
Edge-injective and edge-surjective vertex labellings. - In: SIAM journal on discrete mathematics, ISSN 1095-7146, Bd. 24 (2010), 2, S. 666-683

https://doi.org/10.1137/080723065
Scheide, Diego; Stiebitz, Michael;
Vizing's coloring algorithm and the fan number. - In: Journal of graph theory, ISSN 1097-0118, Bd. 65 (2010), 2, S. 115-138

https://doi.org/10.1002/jgt.20469
Kostochka, Alexandr V.; Král', Daniel; Sereni, Jean-Sébastien; Stiebitz, Michael
Graphs with bounded tree-width and large odd-girth are almost bipartite. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, Bd. 100 (2010), 6, S. 554-559

http://dx.doi.org/10.1016/j.jctb.2010.04.004
Löwenstein, Christian;
In the complement of a dominating set, 2010. - Online-Ressource (PDF-Datei: 101 S.,793 KB) : Ilmenau, Techn. Univ., Diss., 2010
Parallel als Druckausg. erschienen

Eine Menge von Ecken D eines Graphen G=(V,E) ist eine Dominanzmenge, falls jede Ecke aus V\D mindestens einen Nachbarn in D hat. Die disjunkte Dominazzahl eines Graphen G ist die minimale Kardinalität zweier disjunkter Dominanzmengen von G. Wir beweisen untere Schranken für die disjunkte Dominanzzahl für Graphen mit Minimalgrad 2, für Graphen mit großem Minimalgrad und für kubische Graphen.Eine Menge von Ecken T eines Graphen G=(V,E) ist eine totale Dominanzmenge, falls jede Ecke aus V mindestens einen Nachbarn in T hat. Wir charakterisieren Graphen mit Minimalgrad 2 ohne induzierten 5-Kreisen und Graphen mit Minimalgrad mindestens 3, die eine Dominanzmenge, eine totale Dominanzmenge und eine nichtleere Eckenmenge, die paarweise disjunkt sind, haben.Eine Menge von Ecken I eines Graphen G=(V,E) ist eine unabhängige Menge, falls alle Ecken aus I paarweise in G nicht benachbart sind. Wir geben eine konstruktive Charakterisierung für Bäume an, die eine maximale unabhänige Menge und eine dazu disjunkte minimale Dominanzmenge haben und wir zeigen, dass das zugehörige Entscheidungsproblem für allgemene Graphen NP-schwer ist. Zusätzlich zeigen wir mehrere strukturelle Ergebnisse und Komplexitätsergebnisse betreffend Paare disjunkter Mengen, die dominierend, unabhängig oder beides sind. Weiter beweisen wir untere Schranken für die maximale Kardinalität einer unabhängigen Menge von Graphen, die einen kleinen Durchschnittsgrad und keine kurzen Kreise ungerader Länge haben.Ein zusammenhängender Graph G hat spanning tree congestion höchstens s, falls G einen aufspannenden Baum T hat, so dass für jede Kante e von T der Kantenschnitt, der in G definiert ist durch die zwei Komponenten von T-e, höchstens s Kanten enthält. Wir beweisen, dass jeder zusammenhängneder Graph der Ordnung n spanning tree congestion höchstens n^(3/2) hat und wir zeigen, dass das zugehörige Entscheidungsproblem NP-schwer ist.



http://www.db-thueringen.de/servlets/DocumentServlet?id=16280
Scheide, Diego;
Graph edge colouring: Tashkinov trees and Goldberg's conjecture. - In: Journal of combinatorial theory. . - Orlando, Fla. : Academic Press, 1971- , ZDB-ID: 1469158-9, 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, Bd. 310 (2010), 2, S. 199-205

http://dx.doi.org/10.1016/j.disc.2008.09.013
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, ISSN 1095-7146, Bd. 23 (2009), 3, S. 1465-1483

https://doi.org/10.1137/080723843
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
Böhme, Thomas; Schreyer, Jens;
A game theoretic approach to graph problems. - In: 9th International Conference on Innovative Internet Community Systems, I2CS 2009, (2009), S. 149-156