[In der kurz zuvor verteilten Ankuendigung dieses Vortrags wurde ein falscher Raum genannt. Ausserdem hatten sich im Abstract kleine Fehler eingeschlichen. Bitte beachten Sie bei Interesse an diesem Vortrag ausschliesslich diese Mail.]

Die Dozenten der Informatik-Institute der Technischen Universität Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem Vortrag ein:

Prof. Dr. Günther Stiege, Universität Oldenburg: Höherer Zusammenhang in allgemeinen Graphen

Beginn: 14.12.2009, 17:00 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 1. OG, Hörsaal M 160 Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2009-12-14-stiege.html Kontakt: Prof. Dr.-Ing. F. M. Wahl

Allgemeine Graphen enthalten ungerichtete Kanten und gerichtete Bögen in beliebiger Mischung. Sie eignen sich gut für eine einheitliche Darstellung der Graphentheorie. In a-Wegen in allgemeinen Graphen dürfen Bögen in beliebiger Richtung durchlaufen werden. Bei f-Wegen ist der Durchlauf nur vom Anfangsknoten zum Endknoten gestattet. k-facher Zusammenhang wird definiert durch gegenseitige Erreichbarkeit auf mindestens k unabhängigen Wegen. Maximale k-zusammenhängende Untergraphen heißen k-Komponenten, wenn die Wege keine gemeinsamen inneren Knoten haben, und k-Linienkomponenten, wenn sie keine gemeinsamen Kanten/Bögen haben.

Gesucht ist die Zerlegung eines allgemeinen Graphen in k-Komponenten und k-Linienkomponenten für k=1,2,... sowohl für a-Wege als auch für f-Wege. Für k>3 ist der Satz von Menger die Basis der Zerlegungsalgorithmen. k-Linienkomponenten lassen sich in polynomieller Zeit finden. Bei k-Komponenten ist offen, ob sie in polynomieller Zeit gefunden werden können.