User Tools

Site Tools


teaching:ws1920:pg-ca

Projektgruppe: Graphalgorithmen

BA-INF 051: Lineare Programme für Spannbaum- und Steinerbaumprobleme mit Hop Constraints

UPDATE (01.10.2019): Ein Treffen zur Vorbesprechung findet am 10.10.2019 von 14:00 bis 15:30 Uhr in Raum 2.074 statt.

Um abschätzen zu können, ob der Raum große genug ist, schreiben Sie bitte eine kurze formlose E-Mail an Adalat Jabrayilov (Betreff PG-GA reicht aus).

Wann Wo DozentInnen
Vorbesprechung10.10.2019 14:00-15:30 Uhr 2.074 Prof. Dr. Petra Mutzel, Adalat Jabrayilov
Wöchtentliches Treffen Wird bei der Vorbesprechung festgelegt 2.050
Treffen 29.10.2019 14:15 - 15:45 Uhr U1.012
Treffen 05.11.2019 14:15 - 15:45 Uhr U.027

Inhalt:
Das kleinste Spannbaum- bzw. Steinerbaumproblem mit sogenannten Hop Constraints (HMST/HSTP) stammen aus Telekommunikations-Anwendungen und sind NP-schwierige Probleme. Bei diesen Anwendungen ist ein kostenminimaler Teilbaum des Netzwerkes gesucht, der einige Klient-Knoten mit dem Server-Knoten verbindet, so dass die Anzahl der Verbindungskanten zwischen jedem Klient und dem Server das gegebenen Hop-Limit nicht überschreitet. Wenn der Baum alle Knoten mit dem Server verbinden muss, dann spricht man von Spannbaum, sonst von Steinerbaum.

In dieser PG werden ausgewählte Formulierungen mittels ganzzahliger linearer Programmierung für beide Probleme (HMST und HSTP) in die Praxis umgesetzt. Das Ziel ist es, ihre experimentelle Güte und die jeweiligen Laufzeiten zu evaluieren. Als Programmiersprachen werden Python oder Java benutzt. Kenntnisse der linearen Optimierung sind hilfreich.

Mehr

teaching/ws1920/pg-ca.txt · Last modified: 2019/11/04 15:01 by jonas.charfreitag

Page Tools