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 content of the module
  • 11103: Analysis I
  • 11104: Analysis II
  • 12868: Algorithmische Diskrete Mathematik
Mandatory Prerequisites:None
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:Final Module Examination (MAP)
Assessment Mode for Module Examination:
  • Written examination, 90 min. OR
  • Oral examination, 30 min.
It will be announced in the first class whether the examination will organized in written or oral form.
Evaluation of Module Examination:Performance Verification – graded
Limited Number of Participants:None
Part of the Study Programme:
  • no assignment
Remarks:
  • Study programme Mathematics M.Sc.: Compulsory elective module in complex „Analysis / Algebra / Combinatorics“
  • Study programme Mathematik B.Sc.: Compulsory elective module in complex „Vertiefung“, in limited extend 
  • Study programme Wirtschaftsmathematics B.Sc.: Compulsory elective module in complex „Vertiefung“, in limited extend
  • Study programme Informatik B.Sc.: Compulsory elective module in „Mathematik“ or in field of application „Mathematik“
  • Study programme Informatik M.Sc.: Compulsory elective module in „Mathematik“ or in field of application „Mathematik“
Module Components:
  • Lecture: Algorithmic Graph Theory
  • Accompanying exercises
  • Related examination
Components to be offered in the Current Semester:
  • no assignment