Stud.IP Uni Oldenburg
University of Oldenburg
22.11.2019 18:14:51
inf405 - Algorithmic Graph Theory (Complete module description)
Original version English Download as PDF
Module label Algorithmic Graph Theory
Module code inf405
Credit points 6.0 KP
Workload 180 h
Faculty/Institute Department of Computing Science
Used in course of study
  • Bachelor's Programme Computing Science (Bachelor) >
  • Dual-Subject Bachelor's Programme Computing Science (Bachelor) >
  • Master of Education Programme (Gymnasium) Computing Science (Master of Education) >
Contact person
Module responsibility
Authorized examiners
Entry requirements
Skills to be acquired in this module
Graphs are the most frequently used abstraction in computer science. Every system which consists of discrete states or objects and relations between these can be modelled as a graph. Most applications require efficient algorithms to process such graphs (Turau, 1996). This module provides typical graph theory problems and algorithmic solutions. They are discussed with regard to their efficiency and applicability and many of the algorithms will be implemented. An important aspect of this module is to consider different approaches to problems and learn different solution strategies.

Professional competence
The students:
  • identify basic terms of graph theory and optimization and illustrate them with examples
  • name typical graph theory problems and algorithmic solutions
  • identify situations where graph algorithms can be applied
  • discuss typical graph theory problems and algorithmic solutions with regard to their efficiency and applicability.
  • implement graph algorithms
  • know proof strategies and are able to apply them


Methodological competence
The students:
  • extend their knowledge about algorithms and their complexity
  • develop their programming skills
  • expand their range of methods of mathematical modelling


Social competence
The students:
  • use the language of mathematics to discuss problems in groups with different knowledge levels
  • present their ideas in a comprehensible way
  • Expand and improve their own ideas through the comments of their fellow students


Self-competence
The students:
  • reflect their knowledge about algorithms and their complexity
  • develop appropriate solutions for given problems
  • challenge methods of resolution
Module contents
A) Trees
B) Search Algorithms
C) Graph Coloring
D) Flows in Networks
E) Applications of Network Algorithms
F) Shortest Paths
G) Approximation Algorithms
G) Approximation Algorithms
Reader's advisory
Jungnickel, Dieter: Graphs, Networks and Algorithms. Springer, Berlin,
Heidelberg, 4th edition, 2013. Available as an E-Book in BIS.
A detailed bibliography is contained in the lecture notes of this module.
Links
Language of instruction German
Duration (semesters) 1 Semester
Module frequency jährlich
Module capacity unlimited
Modullevel AS (Akzentsetzung / Accentuation)
Modulart je nach Studiengang Pflicht oder Wahlpflicht
Lern-/Lehrform / Type of program V+Ü
Vorkenntnisse / Previous knowledge Grundveranstaltungen Mathematik und Informatik
Course type Comment SWS Frequency Workload attendance
Lecture 3.00 SuSe 42 h
Exercises 1.00 SuSe 14 h
Total time of attendance for the module 56 h
Examination Time of examination Type of examination
Final exam of module
At the end of the lecture period
Written exam