Wir freuen uns über Ihr Interesse. Wenn Sie überlegen an der Projektgruppe teilzunehmen, schreiben Sie bitte eine unverbindliche formlose Email bis zum 5.4.2022 an Adalat Jabrayilov, damit wir die zu erwartende Teilnehmerzahl abschätzen können. Da die Teilnehmerzahl begrenzt ist, werden die Plätze nach Eingang der Emails vergeben. Die Anmeldung per Mail ist unverbindlich. Eine verbindliche Anmeldung erfolgt bis zum 13.4.22.

Direkt vorher findet die Vorbesprechung der PG Algorithm Engineering statt. Sie können an beiden Vorbesprechungen teilnehmen und sich im Anschluss entscheiden an welcher PG Sie teilnehmen wollen. Sollten Sie Interesse an beiden PGs haben, schreiben Sie bitte beiden Betreuern eine Email.

Das Graphfärbungsproblem (en. Vertex Coloring Problem(VCP)) ist ein klassisches kombinatorisches Optimierungsproblem. Dieses Problem sucht nach der minimalen Anzahl von Farben, die benötigt werden, um alle Knoten eines Graphen so einzufärben, dass die benachbarten Knoten unterschiedliche Farben haben.

In dieser Projektgruppe werden wir einen kürzlich veröffentlichten Ansatz für dieses NP-schwierige Problem kennenlernen. Der neue Ansatz benutzt die so genannten OBDDs (Ordered Binary Decision Diagram), wobei die OBDDs ursprünglich zur Darstellung boolescher Funktionen beim Schaltungsentwurf verwendet wurden. Das Ziel ist es, einige auf OBDD basierte Modelle zu implementieren, ihre experimentelle Güte und die jeweiligen Laufzeiten zu evaluieren. Als Programmiersprachen werden Python oder Java benutzt. Kenntnisse der linearen Optimierung sind hilfreich.

Voraussetzung: Kenntnisse der Vorlesung Graphenalgorithmen.

Weitere Informationen folgen demnächst.