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

390036 UK VGSCO Spectral Graph Theory and Algorithms (2017S)

Prüfungsimmanente Lehrveranstaltung

An/Abmeldung

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

Details

max. 50 Teilnehmer*innen
Sprache: Englisch

Lehrende

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

Montag 19.06. 10:00 - 12:00 Seminarraum 4 Oskar-Morgenstern-Platz 1 1.Stock
Dienstag 20.06. 13:30 - 15:30 PC-Seminarraum 1 Oskar-Morgenstern-Platz 1 1.Untergeschoß
Mittwoch 21.06. 10:00 - 12:00 Seminarraum 4 Oskar-Morgenstern-Platz 1 1.Stock
Donnerstag 22.06. 10:00 - 12:00 Studierzone
Freitag 23.06. 10:00 - 12:00 Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß
Montag 26.06. 10:00 - 12:00 Seminarraum 4 Oskar-Morgenstern-Platz 1 1.Stock
Dienstag 27.06. 13:30 - 15:30 PC-Seminarraum 1 Oskar-Morgenstern-Platz 1 1.Untergeschoß
Mittwoch 28.06. 10:00 - 12:00 Seminarraum 4 Oskar-Morgenstern-Platz 1 1.Stock
Donnerstag 29.06. 10:00 - 12:00 Studierzone
Freitag 30.06. 10:00 - 12:00 Seminarraum 1 Oskar-Morgenstern-Platz 1 Erdgeschoß

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

We will give an overview of the surprising connection between the eigenvalues and eigenvectors of graphs expressed as matrices, and classical questions in graph theory, such as bipartiteness, planarity, cliques, colorings, cuts, flows, paths, and walks. Both older structural results and recent algorithmic results will be presented. Topics to be covered include the matrix-tree theorem, Cheeger's inequality, Trevisan's max cut algorithm, bounds on random walks, Laplacian solvers, electrical flow and its applications to max flow.

Art der Leistungskontrolle und erlaubte Hilfsmittel

Mindestanforderungen und Beurteilungsmaßstab

Prüfungsstoff

Literatur


Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Mo 07.09.2020 15:46