Aufgabenstellung für eine Projektarbeit

Parallele Algorithmen zur Lösung des CLIQUE-Problems

Betreuer: Renate Winter und Holger Blaar



Allgemeiner Rahmen

Bekannte sequentielle Algorithmen zur Lösung NP-vollständiger Probleme, wie z. B. des CLIQUE-Problems, erfordern exponentielle Rechenzeit, so daß sie für große Eingabe-Datenmengen unpraktikabel sind.

Es sollen Wege zur effektiven Rechenzeitverkürzung aufgezeigt werden:

  • Literaturauswertung
  • Implementierung von parallelen Algorithmen zur Lösung des CLIQUE-Problems
  • Realisierung eigener Ideen zur Parallelisierung mit Komplexitätsbetrachtung
  • Testrechnungen und Vergleiche hinsichtlich Rechenzeit und verwendeter Prozessorenzahl

    Eine Weiterführung der Projektarbeit in Form einer Diplomarbeit ist möglich.

    Größe der Projektgruppe: 2 Studentinnen bzw. Studenten

    12. 06. 1998