Universität Wien

040968 UK Graph Algorithms and Network Flows (MA) (2022S)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Continuous assessment of course work
Moodle

Registration/Deregistration

Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).

Details

max. 50 participants
Language: English

Lecturers

Classes (iCal) - next class is marked with N

  • Wednesday 02.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 09.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 16.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 23.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 30.03. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 06.04. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 27.04. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 04.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 11.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 18.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 25.05. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 01.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 08.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 15.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 22.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 29.06. 13:15 - 14:45 Hörsaal 8 Oskar-Morgenstern-Platz 1 1.Stock

Information

Aims, contents and method of the course

Basics of the theory of graphs. Recap of lienar programming and branch-and bound methods.

Matching problems, shortest paths, maximal flows, spanning trees, connected components, longest paths and network planning.
Characteristic parameters of networks, such as diameter, centrality and edge weights.

Complexity of graphtheoretic Algorithms

Applications in routing, network design, activity planning, systemic risk, social networks

Assessment and permitted materials

Solving assigned exercises and uploading them in Moodle. final oral exam.

Minimum requirements and assessment criteria

A minimum of 60% corretly solved exercised + oral exam

Examination topics

what has been presented. Handouts will be available.

Reading list

- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 1990
- D. Jungnickel: Graphen, Netzwerke und Algorithmen, BI Wissenschaftsverlag, 3. Auflage, 1994
- J. Bang-Jensen, G. Gutin: Digraphs: Theory, Algorithms and Applications, Springer, 2001
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993
- D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010
- E. Tardos, J. Kleinberg, Algorithm Design, Addison Wesley, 2005

Association in the course directory

Last modified: Th 03.03.2022 16:08