Bachelorarbeiten: Dominating Set und Independent Set auf Graphklassen

Wir bieten 20 Bachelorarbeiten im Bereich Algorithm Engineering an. Alle Arbeiten behandeln eines von zwei Problemen – Minimum Dominating Set oder Maximum Independent Set – auf jeweils einer Graphklasse. Sie recherchieren geeignete Algorithmen, implementieren mehrere davon, erzeugen eigene Testinstanzen, vergleichen die Verfahren systematisch und entwickeln daraus einen auf Ihre Graphklasse zugeschnittenen Löser.

Die Themenvergabe wird im Ersttermin am 1.10.2026 besprochen und erfolgt im Anschluss über Moodle.

Voraussetzungen

Nach BPO benötigen Sie für die Anmeldung der Bachelorarbeit mindestens 120 Leistungspunkte. Darüber hinaus setzen wir voraus, dass die Pflichtmodule der ersten Semester bestanden sind: DAP 1/2, RS, GTI bzw. TIfAI sowie die Mathematik-Module MafI 1/2 bzw. HM 1–3. Einen Nachweis darüber, etwa eine aktuelle Leistungsübersicht, legen Sie uns spätestens zur Anmeldung der Arbeit vor.

Fachlich erwarten wir sicheren Umgang mit einer Programmiersprache Ihrer Wahl sowie Grundkenntnisse in Algorithmen und Komplexität. Vorkenntnisse zur jeweiligen Graphklasse werden nicht erwartet.

Die Arbeit kann auf Deutsch oder auf Englisch verfasst werden. Die Sprachwahl hat keinen Einfluss auf die Bewertung.

Termine

Alle gemeinsamen Termine finden in OH14/R202 statt und sind verbindlich. An den Vortragsterminen ist die Anwesenheit über den gesamten Termin erforderlich, also auch bei den Vorträgen der anderen Teilnehmenden.

Do, 1. Oktober 2026, 10:30 Uhr – Ersttermin. Vorstellung beider Probleme und der 20 Themen, Ablauf, Anforderungen. Die Themenvergabe wird hier besprochen und folgt im Anschluss über Moodle.
bis Do, 15. Oktober 2026 – Stichtag Anmeldung. Die Arbeit muss bis zu diesem Tag angemeldet sein. Ohne fristgerechte Anmeldung ist eine Teilnahme nicht möglich.
Do, 12. und Do, 19. November 2026, je ab 9:15 Uhr – Einführungsvorträge (10 Minuten je Person): Definition der eigenen Graphklasse und Vorstellung der ausgewählten Verfahren.
Mo, 14. bis Fr, 18. Dezember 2026 – Einzeltermine (20 Minuten, individuelle Terminvergabe): Besprechung der Experimentergebnisse und der Konsequenzen für den eigenen Löser.
Do, 21. Januar 2027 – Fragetermin. Offene Sprechstunde zur Verschriftlichung.
Do, 18. und Do, 25. Februar 2027 – Abschlussvorträge.

Themen

Acht der Graphklassen werden mit beiden Problemen bearbeitet. Definitionen und Instanzgeneratoren können die beiden Bearbeitenden einer Klasse gemeinsam erarbeiten; die Ergebnisse hängen nicht voneinander ab.

Cluster A – Strukturelle Sparsity und Zerlegungen

Minimum Dominating Set auf planaren Graphen
Minimum Dominating Set auf Graphen beschränkter Baumweite
Minimum Dominating Set auf Intervall- und chordalen Graphen
Minimum Dominating Set auf d-degenerierten Graphen und Graphen beschränkten Grades
Maximum Independent Set auf planaren Graphen
Maximum Independent Set auf Graphen beschränkter Baumweite
Maximum Independent Set auf d-degenerierten Graphen und Graphen beschränkten Grades
Maximum Independent Set auf Intervall-, chordalen und Permutationsgraphen

Cluster B – Geometrische Graphen

Minimum Dominating Set auf Disk Graphs: vom Unit-Fall zu beliebigen Radien
Minimum Dominating Set auf Gitter- und Polyomino-Graphen
Minimum Dominating Set auf Delaunay-Graphen und der Proximity-Hierarchie
Maximum Independent Set auf Disk Graphs: vom Unit-Fall zu beliebigen Radien
Maximum Independent Set auf Rechteck- und Quadrat-Schnittgraphen
Maximum Independent Set auf Gitter- und Polyomino-Graphen

Cluster C – Zufallsmodelle

Minimum Dominating Set auf hyperbolischen Zufallsgraphen
Minimum Dominating Set auf Potenzgesetz-Graphen (Chung–Lu, Preferential Attachment)
Minimum Dominating Set auf Random Intersection Graphs
Maximum Independent Set auf Erdős–Rényi-Graphen
Maximum Independent Set auf hyperbolischen Zufallsgraphen
Maximum Independent Set auf Random Intersection Graphs

Bei Fragen wenden Sie sich gerne vorab an uns und kommen Sie zum Ersttermin.