GraphBench

Inhalt

Entscheidungsprobleme

• Erfüllbarkeit (screenshot)
• Clique (screenshot)
• Vertex cover (screenshot)
• Independent set (screenshot)
• Graph Färbbarkeit (screenshot)
• Hamilton circuit (screenshot)
• 3 Dimensional Matching (screenshot)

Optimierungsprobleme

• Traveling salesman (screenshot)

Problemreduktionen

• Erfüllbarkeit - 3-CNF Erfüllbarkeit
• Vertex cover - Clique (screenshot)
• Vertex cover - Independent set (screenshot)
• Independent set - Clique (screenshot)
• Vertex cover - Hamiltonian Circuit (screenshot)
• Hamiltonian Circuit - Traveling Salesman (screenshot)
• Graph Färbbarkeit - Erfüllbarkeit (screenshot)
• Erfüllbarkeit - Graph Färbbarkeit (screenshot)
• Erfüllbarkeit - Clique (screenshot)
• Erfüllbarkeit - Vertex cover (screenshot)

Programmierumgebung

• Toolbox: schreiben von Algorithmen in Java (screenshot)