Arbeitsgruppe Theoretische Informatik

Implementierung und Vergleich exakter paralleler Algorithmen für Vertex Cover

Ansprechpartner: Malte Skambath 

Das Vertex-Cover- oder Knotenüberdeckungsproblem [1] ist ein Standardbeispiel für ein NP vollständiges und insbesondere auch FPT Problem [2]: Gegeben ein Graph und eine Zahl k, gibt es eine Knotenmenge (das Vertex-Cover) aus dem Graphen mit höchstens k Knoten, sodass jede Kante mindestens einen Knoten aus der Menge besitzt, also abgedeckt ist.

Im Rahmen dieser Arbeit sollen parametresierte parallele Algorithmen für Vertex Cover implementiert und verglichen werden.

Quellen

  1. Wikipedia (EN): Vertex Cover
  2. Wikipedia: Parametrisierter Algorithmus