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

Grundlagen der Graphentheorie. Rekapitulieren von linearer Programmierung und Branch-and-bound methoden.

Zuordnungsprobleme, kürzeste Wege, Maximale Flüsse, Spannende Bäume, Zusammenhangskomponenten, längste Pfade und Netzplantechnik.

Charakteristische Maßzahlen eines Graphen. wie Durchmesser, Zentralität, Kantengewichte, etc.

Komplexität von graphentheortischen Algorithmen.

Anwendungen in der Routenplanung, Netzwerk design, Netzplantechnik, systemisches Risiko und soziale Netzwwerke.
social networks

Applications Networks are apparent in our daily lives. Typical examples are: electrical and power networks, data networks, traffic networks (streets, rails, airline routes), manufacturing and distribution networks, and (online) social networks.
Graphs are used to model these networks in an abstract way and allow to efficiently solve problems on networks by using standardized graph algorithms.
In detail we discuss:
- matchings (stable marriage problem)
- computational complexity
- graph connectivity and search algorithms
- maximum flows
- shortest paths
Furthermore, we consider tools and algorithms for (social) network analysis:
- community detection
- partitioning and clustering
- strong and weak ties
- positive and negative relationships

The goals of this course are to:
- understand the fundamental concepts of networks
- understand basic graph algorithms
- be able to apply algorithms to network based problems
- be able to analyze networks based on different measures

The methods for knowledge transfer and gain are:
- lectures
- joint discussions of exercises and according solutions
- practical implementation of algorithms