14274 - Algorithmic Graph Theory Modulübersicht

Module Number: 14274
Module Title:Algorithmic Graph Theory
  Algorithmische Graphentheorie
Department: Faculty 1 - Mathematics, Computer Science, Physics, Electrical Engineering and Information Technology
Responsible Staff Member:
  • Prof. Dr. rer. nat. habil. Köhler, Ekkehard
Language of Teaching / Examination:English
Duration:1 semester
Frequency of Offer: On special announcement
Credits: 8
Learning Outcome: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.
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
Recommended Prerequisites:

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)
Mandatory Prerequisites:

No successful participation in module 11405 - Algorithmische Graphentheorie

Forms of Teaching and Proportion:
  • Lecture / 4 Hours per Week per Semester
  • Exercise / 2 Hours per Week per Semester
  • Self organised studies / 150 Hours
Teaching Materials and Literature:
  • 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)
Module Examination:Prerequisite + Final Module Examination (MAP)
Assessment Mode for Module Examination:

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.

Evaluation of Module Examination:Performance Verification – graded
Limited Number of Participants:None
Part of the Study Programme:
  • Master (research-oriented) / Artificial Intelligence / PO 2022 - 1. SÄ 2024
  • Master (research-oriented) / Mathematical Data Science / PO 2025
  • Master (research-oriented) / Mathematics / PO 2025
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”
Module Components:
  • Lecture: Algorithmic Graph Theory
  • Accompanying exercises
  • Related examination
Components to be offered in the Current Semester: