Algorithmische Graphentheorie
Algorithmic Graph Theory
8 CPirregularlyDE
Prerequisites
Mandatory, as written
Keine Teilnahme an Modul • 14274 Algorithmic Graph Theory
Recommended, as written
Kenntnis des Stoffes der Module • 11101 Lineare Algebra und analytische Geometrie I • 12868 Algorithmische Diskrete Mathematik oder der Module • 11112 Mathematik IT-1 (Diskrete Mathematik) • 11113 Mathematik IT-2 (Lineare Algebra)
Contents
Erkennungs-/ Optimierungsalgorithmen für verschiedene Graphenklassen, strukturelle Eigenschaften von Graphen zum Entwurf effizienter Algorithmen (z.B. Baumweite von Graphen), Intervallgraphen, chordale Graphen, planare Graphen
Learning outcomes
Die Studierenden sollen • weitere Kenntnisse über Zusammenhänge und Methoden der Graphenthorie erwerben • algorithmische Problemstellungen der Graphentheorie verstehen und so einen wichtigen Beitrag zur weiteren Ausprägung algorithmischen Denkens leisten • geeignete Verfahren zur Lösung dieser Problemstellungen kennen und anwenden können • am Beispiel von Themen zur Graphentheorie Erfahrungen im selbstständigen wissenschaftlichen Arbeiten gewinnen.
Assessment
Voraussetzung für die Modulabschlussprüfung: • erfolgreiche Bearbeitung von Hausaufgaben (zweiwöchentlich) oder erfolgreiche Bearbeitung von Hörsaaltests (ca. 4 je 15-30 Minuten) Modulabschlussprüfung: • Klausur, 90 min. ODER • mündliche Prüfung, 30 min. In der ersten Lehrveranstaltung wird bekanntgegeben, wie die Voraussetzung organisiert wird und ob die Prüfungsleistung in schriftlicher oder mündlicher Form zu erbringen ist.
Literature (4)
- M.C. Golumbic: Algorithmic Graph Theory and Perfect Graphs. (Academic Press, 1980)
- A. Brandstädt, V.B. Le, J.P. Spinrad: Graph Classes: A Survey. (SIAM, 1999)
- D.B. West: Introduction to Graph Theory - 2nd ed. (Prentice Hall, 2001)
- J.P. Spinrad: Efficient Graph Representations. (ACM, 2003)
Remarks
• Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Analysis / Algebra / Kombinatorik" • Studiengang Mathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung”, im begrenzten Umfang • Studiengang Wirtschaftsmathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung”, im begrenzten Umfang • Studiengang Künstliche Intellgenz B.Sc.: Wahlpflichtmodul im Komplex „Wissensakquise, -repräsentation und -verarbeitung” • Studiengang Informatik B.Sc.: Wahlpflichtmodul in „Praktische Mathematik" oder im Anwendungsfach „Mathematik” • Studiengang Informatik M.Sc.: Wahlpflichtmodul in „Mathematik" oder im Anwendungsfach „Mathematik”
Source: BTU's module description · retrieved 27 Sep 2026Original