GraphBench

GraphBench ist eine Lernumgebung für NP-Vollständigkeit und beinhaltet typische NP-vollständige Probleme (z.B. Traveling salesman, Satisfiability or 3-Dimensional Matching) und Reduktionen (z.B. Satisfiability nach Clique). GraphBench ist eine hochgradig interaktive Lernsoftware und vermittelt das Thema auf eine intuitive Art.

GraphBench beinhaltet verschiedene Lösungsalgorithmen (d.h. erschöpfende Suche und Heuristiken) für die verschiedenen NP-vollständigen Probleme. Die Algorithmen kommen mit verschiedenen graphischen Visualisierungen. Zusätzliche enthält GraphBench eine Programmierumgebunge die es Studenten erlaubt, eigene Graphen Algorithmen zu schreiben.

GraphBench ist eine Java-Anwendung und kann kostenlos heruntergeladen werden.

Hinweis 29. August 2008: Das Speichern und Laden von Dateien funktioniert mit Java 6, wenn Graphbench in einer Shell mit folgendem Befehl gestartet wird: java -version:1.5 -jar graphbench.jar. Herzlichen Dank an Thomas Roch für diesen Hinweis.

Screenshots

Idee, Konzeption & Realisierung: Jürg Nievergelt, Markus Brändle, Matthias Dreier. Mit Beiträgen von Raimond Reichert, Werner Hartmann und Bertrand Meyer.

Kontakt: Markus Brändle, graphbench[at]markusbraendle.ch