50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Events 1999


Academydays

Talks

  • 26. Mai 1999, 17.15 Uhr, Hörsaal H1, SFS
    Prof. Dr. Andreas Brandstaedt, Uni Rostock
    Graphenklassen und Algorithmen

    Viele Modellbildungen der Informatik verwenden Graphen oder Hypergraphen und führen zu algorithmischen Problemen auf solchen Objekten. Typische Beispiele sind Färbungsprobleme oder das bekannte Hamiltonkreisproblem. Algorithmische Graphenprobleme sind in vielen Fallen NP-vollständig; aufgrund ihrer Wichtigkeit muss man dennoch nach effizienten Methoden zu ihrer Lösung suchen. Hierbei gibt es verschiedene Möglichkeiten wie Approximation, stochastische Algorithmen oder Einschränkung auf spezielle Eingaben. Letzteres soll hier genauer behandelt werden. Für eine Vielzahl von speziellen Graphenklassen ist die Komplexität algorithmischer Probleme untersucht worden, und es gibt eine Reihe von Struktureigenschaften, die zu effizienten Verfahren führen. Von besonderem Interesse sind Verallgemeinerungen von Bäumen in verschiedener Hinsicht, insbesondere chordale Graphen und ihre Varianten. Eine wichtige Rolle spielen spezielle Knotenreihenfolgen von Graphen. Breitensuche (BFS) und insbesondere Lexiographische Breitensuche (LexBFS) sind Verfahren, die zu interessanten Knotenreihenfolgen führen und in verschiedenen Fällen die Lösung von algorithmischen Problemen entlang der Knotenreihenfolge ermöglichen. Zum Abschluss soll auf eine neue Monographie zu Graphenklassen sowie auf ein Internet-Informationssystem zur Inklusion von Graphenklassen hingewiesen werden.