Kantenordnungen

05. November 2018

Vortragsreihe: Fakultätskolloquium MI

Zeitraum
05.11.2018
17:00 Uhr (bis ca. 19 Uhr)

Ort
FernUniversität, Gebäude 3 (Informatikzentrum), Raum Ellipse (EG), Universitätsstr. 11, 58097 Hagen

Veranstalter/-in
Fakultät für Mathematik und Informatik

Referent/-in
Dr. Lena Schlipf
FernUniversität
Wissenschaftliche Mitarbeiterin im Lehrgebiet Theoretische Informatik (Prof. Dr. André Schulz)

Auskunft erteilt
Dekanatsbüro der Fakultät für Mathematik und Informatik

Im Rahmen der öffentlichen Vortragsveranstaltung verleiht die Fakultät Mathematik und Informatik ihren Fakultätspreis an Dr. Lena Schlipf.

Die Veranstaltung richtet sich an die gesamte Hochschulöffentlichkeit, an externe Fachleute und Bürgerinnen und Bürger, die am Vortragsthema interessiert sind.


In der algorithmischen Graphentheorie werden schon seit Jahrzehnten Konzepte als zentrales Werkzeug verwendet, die Graphen in Teilgraphen zerlegen, wobei die einzelnen Teile einen vorgegebenen Knotenzusammenhang erfüllen. Bekannte Konzepte sind z.B. kanonische Ordnungen.

Trotz des sehr großen Interesses an kanonischen Ordnungen ist kein analoges Konzept für Kantenzusammenhang bekannt. In diesem Vortrag werden wir so ein Konzept, Kantenordnung genannt, kennenlernen. Wir werden sehen, wie man (1,1)-Kantenordnungen von 2-kantenzusammenhängenden Graphen, ebenso wie (2,1)-Kantenordnungen von 3-kantenzusammenhängenden Graphen, in linearer Zeit berechnen kann.

Als erste Anwendung für dieses neue Konzept, werden wir uns die berühmte Vermutung über (kanten)unabhängige Spannbäume anschauen. Die Vermutung sagt aus, dass jeder k-kantenzusammenhängende Graph k gewurzelte Spannbäume enthält, die alle paarweise kantenunabhängig sind. Wir zeigen, wie man sowohl 2- als auch 3-kantenunabhängige Spannbäume in 2- bzw. 3-kantenunabhängigen Graphen in linearer Zeit mit Hilfe von Kantenordnungen berechnen kann. Dies reduziert die Laufzeit für 3-kantenzusammenhängende Graphen drastisch, der zuvor beste Algorithmus hatte eine quadratische Laufzeit.

Die Ergebnisse sind in Zusammenarbeit mit Jens M. Schmidt von der TU Ilmenau entstanden.

Gerd Dapprich | 20.09.2018