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: Mon, 16 Oct 2017 23:04:19 +0200 in 0.0370 sec


Brandt, Stephan; Müttel, Janina; Rautenbach, Dieter; Regen, Friedrich
Minimum degree and density of binary sequences. - In: European journal of combinatorics. - London : Academic Press, Bd. 31 (2010), 7, S. 1936-1945
http://dx.doi.org/10.1016/j.ejc.2010.01.005
Henning, Michael A.; Löwenstein, Christian; Rautenbach, Dieter; Southey, Justin
Disjoint dominating and total dominating sets in graphs. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 158 (2010), 15, S. 1615-1523
http://dx.doi.org/10.1016/j.dam.2010.06.004
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 / B. - Orlando, Fla : Academic Press, Bd. 100 (2010), 6, S. 554-559
http://dx.doi.org/10.1016/j.jctb.2010.04.004
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 : automation, biomedical engineering and computer science ; proceedings ; 55. IWK Internationales Wissenschaftliches Kolloquium ; 13 - 17 September 2010. - Ilmenau : Verl. ISLE / Internationales Wissenschaftliches Kolloquium. Technische Universität Ilmenau ; 55 (Ilmenau) : 2010.09.13-17., ISBN 978-3-938843-53-6, (2010), S. 754-760

http://www.db-thueringen.de/servlets/DocumentServlet?id=17361
Harant, Jochen
A lower bound on independence in terms of degrees. - Ilmenau : Techn. Univ., Inst. für Mathematik. - Online-Ressource (PDF-Datei: 6 S., 173,1 KB). - (Preprint. - M10,08)
http://www.db-thueringen.de/servlets/DocumentServlet?id=16418
Löwenstein, Christian
In the complement of a dominating set. - Online-Ressource (PDF-Datei: 101 S.,793 KB)
Ilmenau : Techn. Univ., Diss., 2010

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
Brandstädt, Andreas; Le, Van Bang; Rautenbach, Dieter
Exact leaf powers. - In: Theoretical computer science : the journal of the EATCS. - Amsterdam [u.a.] : Elsevier, Bd. 411 (2010), 31/33, S. 2968-2977
http://dx.doi.org/10.1016/j.tcs.2010.04.027
Artmann, Sarah
Über die Dominanzzahl in Graphen unter Nutzung verschiedener Konzepte. - Online-Ressource (PDF-Datei: 81 S., 707 KB)
Ilmenau : Techn. Univ., Diss., 2010

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
Göring, Frank; Harant, Jochen
Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 9, S. 1491-1494
http://dx.doi.org/10.1016/j.disc.2009.10.005
Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Regen, Friedrich
Packing edge-disjoint cycles in graphs and the cyclomatic number. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 310 (2010), 9, S. 1456-1462
http://dx.doi.org/10.1016/j.disc.2009.07.017