Algorithmic Graph Theory
Algorithmische Graphentheorie
8 CPirregularlyEN
Prerequisites
Mandatory, as written
No successful participation in module 11405 - Algorithmische Graphentheorie
Recommended, as written
Knowledge of the contents of modules • 11101: Lineare Algebra und analytische Geometrie I • 12868: Algorithmische Diskrete Mathematik or of modules • 11112: Mathematik IT-1 (Diskrete Mathematik) • 11113: Mathematik IT-2 (Lineare Algebra)
Contents
Recognition and optimization algorithms for several graph classes, structural properties of graphs for the design of efficient algorithms (e.g. the treewidth of graphs), interval graphs, chordal graphs, planar graphs
Learning outcomes
After successfully completing the module, students have further knowledge of connections and methods in graph theory. They are able to understand algorithmic problems in graph theory and can thus make an important contribution to the further development of algorithmic thinking. Students know suitable methods for solving these problems and can apply them. Using graph theory topics as examples, they have gained experience in independent scientific work.
Assessment
Prerequisite: • Successful completion of homework (fortnightly) and successful completion of tests (approx. 4 tests of 15-30 minutes each, written during the lecture period) Final module examination: • Written examination, 90 min. OR • Oral examination, 30 min. During the first class meeting, notice will be given on how the prerequisite will be structured and whether the examination will be in written or oral form.
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
• Study programme Mathematics M.Sc.: Compulsory elective module in complex „Analysis / Algebra / Combinatorics” • Study programme Mathematical Data Science M.Sc.: Compulsory elective module in complex „Advanced Mathematical Methods in Data Science” • Study programme Artificial Intelligence M.Sc.: Compulsory elective module in complex „Knowledge Acquisition, Representation, and Processing”
Source: BTU's module description · retrieved 29 Sep 2026Original