Navigation

Springe zum Hauptinhalt
Fakultät für Informatik
Informatik-Kolloquien

130. Informatik-Kolloquium

Chemnitzer Workshop "Algorithmen und Graphen"




Montag, 14.01.2008
15.30 - 18.45 Uhr, 1/346

Vorträge

15.30-16.00 Uhr  Genomdarstellungen und Regenbogenfärbungen
 Prof. Dr. Ingo Schiermeyer (TU Bergakademie Freiberg)
Zur Darstellung eines Genoms werden zwei Haplotypen benötigt. Für eine gegebene Menge von m Genomen wird eine kleinste Menge von Haplotypen gesucht, mit denen sich alle Genome darstellen lassen. Dieses Problem lässt sich als ein Kantenfärbungsproblem formulieren. Gesucht wird dann ein kleinster Untergraph, bei dem jede Farbe (Genom) genau einmal auftritt.

  
16.00-16.30 UhrPolynomielle Algorithmen für F-Unabhängigkeit
 Dr. Frank Göring (TU Chemnitz)
Sei F ein Graph. Eine Knotenmenge S ist F-unabhängig in einem Graphen G, wenn der durch S induzierte Untergraph G[S] keine Kopie von F als Untergraph enthält. Harant, Schiermeyer, Rautenbach, und G. zeigten, dass das Problem zu entscheiden, ob G eine F-unabhängige Menge der Kardinalität k enthält, NP-schwer ist.
Im Vortrag diskutieren wir zwei Graphenklassen, für die es möglich ist eine F-unabhängige Menge mit maximaler Kardinalität in Linearzeit zu finden: Die Klasse von Graphen mit beschränkter Baumweite und die Klasse der gut-F- überdeckten Graphen. Hierbei heißt ein Graph gut-F-überdeckt, wenn die Familie der F-unabhängigen Teilmengen der Knotenmenge ein Matroid formt.
Offene Fragen bzgl. der Klasse der gut-F-überdeckten Graphen werden vorgestellt.
Der Vortrag basiert auf der Diplomarbeit von D. Seidewitz
(http://www.tu-chemnitz.de/mathematik/discrete/diplom/daniel seidewitz.pdf).

  
17.15-17.45 UhrHeuristiken und exakte Algorithmen für das verallgemeinerte Traveling Salesman Problem
 Dr. Gerold Jäger ((Martin-Luther-Universität Halle-Wittenberg)
Wir untersuchen folgendes Minimierungsproblem, das wichtige Anwendungen in der Bioinformatik hat. Finde in einem gerichteten Graphen mit n Knoten eine Tour mit minimalen Kosten, wobei die Kosten jedes Knoten dieser Tour direkt von dem linken und rechten Nachbarn in der Tour abhängen. Dieses Problem kann als Verallgemeinerung des asymmetrischen Traveling Salesman Problems (ATSP) angesehen werden. Einerseits ist es schwerer als das ATSP, da es eine dreidimensionale Kostenfunktion besitzt, andererseits kommen bei beiden Problemen ”nur”(n-1)! Touren für die optimale Lösung in Frage.
Wir stellen sowohl Heuristiken als auch exakte Algorithmen zu diesem Problem vor, die teils neue Ansätze, teils naheliegende Erweiterungen von ATSP-Algorithmen sind.

  
17.45-18.15 UhrKnotenpartitionen in stochastischen Netzwerken
 Prof. Dr. Peter Tittmann (Hochschule Mittweida)
Ein wichtiges Problem bei der Analyse sozialer Netzwerke ist die Identifikation von Gruppen in einem Netzwerk. In der Sprache der Graphentheorie suchen wir eine Partition der Knotenmenge, deren Blöcke in sich einen hohen Zusammenhang (geringen Durchmesser, ...) aufweisen, wobei unterschiedliche Blöcke jedoch ”schwach zusammenhängend” sein sollen. F¨ur deterministische Graphen gibt es zahlreiche Maße für die Güte solcher Partitionen. Algorithmen zum Auffinden dieser Cluster basieren zum Beispiel auf Kanten-Betweenness, elektrischen Widerständen, Irrfahrten, Flussproblemen oder spektralen Methoden. In sozialen Netzwerken unterliegen Relationen zwischen Akteuren (Kanten eines Graphen) jedoch oft dem Zufall.
Für Graphen, in denen Kanten mit gegebener Wahrscheinlichkeit existieren, ist die Einführung neuer Kenngrößen erforderlich, die in dem Vortrag vorgestellt werden. Neben den stochastischen Problemen werden wir auch kombinatorische Probleme diskutieren, die sich aus Anzahlbestimmungen von Partitionen ergeben.

  
18.15-18.45 UhrApproximation von Independent Set in zufälligen uniformen Hypergraphen in polynomieller erwarteter Zeit
 Dipl.-Inf. Kai Plociennik (TU Chemnitz)
Für das Problem Independent Set in uniformen Hypergraphen ist bekannt, dass es für kein Î > 0 einen polynomiellen Approximationsalgorithmus mit Güte gibt. Im Vortrag wird ein deterministischer Algorithmus gezeigt, der für ein bestimmtes Modell zufälliger uniformer Hypergraphen eine polynomielle erwartete Laufzeit besitzt, und eine Güte hat, die die Grenze unterbietet.

Alle interessierten Personen sind herzlich eingeladen!

Presseartikel