Publications

Brandt, Stephan;
A note on generalized pentagons. - In: Discrete mathematics, Bd. 310 (2010), 20, S. 2766-2767

http://dx.doi.org/10.1016/j.disc.2010.04.017

Löwenstein, Christian; Rautenbach, Dieter
Pairs of disjoint dominating sets and the minimum degree of graphs. - In: Graphs and combinatorics, ISSN 1435-5914, Bd. 26 (2010), 3, S. 407-424

https://doi.org/10.1007/s00373-010-0918-9

Brandt, Stephan; Müttel, Janina; Rautenbach, Dieter; Regen, Friedrich
Minimum degree and density of binary sequences. - In: European journal of combinatorics, Bd. 31 (2010), 7, S. 1936-1945

https://doi.org/10.1016/j.ejc.2010.01.005

Girlich, Franz; Roßberg, Michael; Schäfer, Günter; Böhme, Thomas; Schreyer, Jens
Scrubbing the Vivaldi network coordinate system. - In: Crossing borders within the ABC, (2010), S. 754-760

http://www.db-thueringen.de/servlets/DocumentServlet?id=17361

Artmann, Sarah;
Über die Dominanzzahl in Graphen unter Nutzung verschiedener Konzepte, 2010. - Online-Ressource (PDF-Datei: 81 S., 707 KB) : Ilmenau, Techn. Univ., Diss., 2010
Parallel als Druckausg. erschienen

Die Dominanzzahl in Graphen ist die minimale Mächtigkeit einer Knotenpunktmenge D, für die jeder Knoten entweder in D enthalten ist oder einen Nachbarn in D besitzt. Da das zugehörige Entscheidungsproblem NP-vollständig ist, versucht man obere Schranken für die Dominanzzahl in verschiedenen Graphenklassen zu finden und diese zu realisieren. Ein Ansatz, zu solchen Schranken zu kommen, ist die probabilistische Methode nach Alon und Spencer. Hierbei werden Knoten mit einer Wahrscheinlichkeit zwischen Null und Eins zu der Menge hinzugenommen und diese dann zu einer dominierenden Menge ergänzt. Mit Hilfe sogenannter Abstiegsverfahren kann man dann für die einzelnen Knoten zu den "realisierenden" Wahrscheinlichkeiten Null und Eins übergehen. Die dabei erzielten Verbesserungen werden bestimmt und so neue Schranken für reguläre und allgemeine Graphen gewonnen. Diese hängen jedoch von der Mächtigkeit einer Menge von Knoten (oder Schranken für diese) ab, die paarweise einen gewissen Abstand voneinander haben. Weiter wird ein verallgemeinerter Ansatz für die Bestimmung der Verbesserung von Schranken für die Dominanzzahl durch Abstiegsverfahren entwickelt. Der in diesem Zusammenhang beschriebene Algorithmus für allgemeine bzw. bipartite Graphen kann für viele multilineare Funktionen, die eine obere Schranke für die Dominanzzahl bilden, angewandt werden und liefert in jedem Fall neue, verbesserte Ergebnisse gegenüber der Ausgangsschranke. Durch die Verallgemeinerung der Methode von Alon und Spencer können zudem direkt bessere Schranken für die Dominanzzahl allgemeiner Graphen erreicht werden. Auf bipartiten Graphen, für die bisher nur wenige eigenständige Schranken bekannt sind, werden weitere Verbesserungen erzielt. Die Resultate werden numerisch ausgewertet und bekannten Schranken gegenüber gestellt.

http://www.db-thueringen.de/servlets/DocumentServlet?id=15940