Universität Wien
Achtung! Das Lehrangebot ist noch nicht vollständig und wird bis Semesterbeginn laufend ergänzt.

040968 UK Graph Algorithms and Network Flows (2011S)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Prüfungsimmanente Lehrveranstaltung

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

max. 30 Teilnehmer*innen
Sprache: Englisch

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

  • Dienstag 01.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 08.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 15.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 22.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 29.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 05.04. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 12.04. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 03.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 10.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 17.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 24.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 31.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 07.06. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 21.06. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
  • Dienstag 28.06. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

Networks are apparent in our daily lives. Think of electrical and power networks, telephone or internet networks, traffic networks (highways, rail networks, airline service networks), manufacturing and distribution networks, or even social networks! In all these examples, we wish to move some entity (electricity, a product, a person, a vehicle, a message, or an advertisement) from point A to point B in that network. Usually, we would like to do that as efficient as possible. And sometimes we want to move many of these items simultaneously through the network. In other words, we are interested in:

* Providing good service to users
* Using the underlying transmission facilities (that are usually very expensive) effectively

Art der Leistungskontrolle und erlaubte Hilfsmittel

- Homework (25%)
- Presentation of a selected topic (15%)
- Oral exam (60%)

At least 60% in total are needed to pass the exam.

Mindestanforderungen und Beurteilungsmaßstab

This course should help graduate students to:

a) understand information about networks, and
b) develop models and algorithms to design, manage and analyse networks.

Prüfungsstoff


1) Graphs.
- Graph Traversal Algorithms. Topological Ordering.
- Dynamic Programming. Shortest Path Algorithms.
- Greedy Algorithms. Minimum Spanning Tree.
- Flow Algorithms.

2) Analysis of social networks
- Graph partitioning (strong and week ties, betweenness measures)
- Networks in their surrounding contexts: homophily, affiliation
- Positive and negative relationships: structural balance, weaker form of structural balance, generalization
- Cascading behavior in networks: diffusion, cascades and clusters. Knowledge, threshold and collective action. The cascade capacity.
- Spreading epidemics in networks: branching process, SIR vs. SIS epidemic model. Analysis of branching process.

Literatur

* Network Flows: Theory, Algorithms, and Applications, by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
* Algorithm Design, by Eva Tardos, Jon Kleinberg
* Networks, Crowds, and Markets: Reasoning About a Highly Connected World, by David Easley and
Jon Kleinberg
http://www.cs.cornell.edu/home/kleinber/networks-book/

Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Mo 07.09.2020 15:29