11. November 1999, Musik- und Kongresshalle (MuK) Lübeck, Willy-Brandt-Allee 10
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.
