Laufzeitmessungen von Graphenalgorithmen

Intervallgraphen treten in zahlreichen Anwendungsgebieten bei der Modellierung von Gegebenheiten in der Natur und im täglichen Leben auf und für diese Graphenklasse lassen sich eine Reihe von allgemeinen NP-vollständiger Probleme in polynomieller Zeit lösen.

Die Eigenschaften von Intervallgraphen lassen ganz unterschiedliche Ansätze für Erkennungsalgorithmen zu, die mit einer linearen Laufzeit auskommen.

Die Erkennungsalgorithmen von Booth und Lueker (1976), von Simon (1992) und von Coreil, Olarin und Stewart (1998) sollen auf ihre Tragfähigkeit hin untersucht werden und in einer einheitlichen Umgebung implementiert werden. Die Implementierungen sind mit geeigneten Testgraphen zu vergleichen.

Vorlesung Graphenalgorithmen

in Bearbeitung