Algorithmen II, Vorlesung, WS 2016/17, 15.11.2016, 08

Autor

Christian Schulz

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

08 |
0:00:00 Starten
0:00:18 Wiederholung Starke Zusammenhangskomponenten
0:05:26 Wiederholung Tiefensuchschema
0:13:12 5 Maximum Flows and Matchings
0:14:57 Definitions: Network
0:16:04 Definitions: Flows
0:18:46 Definitions: (Minimum) s-t Cuts
0:20:12 Duality Between Flows and Cuts
0:21:21 Applications
0:22:11 Applications in our Group
0:22:34 Exkurs: Balanced Bipartitioning
0:27:24 Example
0:28:58 Option 1: linear programming
0:32:33 Algorithms 1956-now
0:34:00 Augmenting Paths (Rough Idea)
0:34:59 Example
0:35:49 Residual Graph
0:38:51 Augmenting Paths
0:39:40 Ford Fulkerson Algorithm
0:59:36 A Bad Example for Ford Fulkerson
1:00:35 An Even Worse Example for Ford Fulkerson
1:03:05 Dinitz Algorithmus
1:19:41 Example
1:20:38 Block Flows Analysis 1
1:22:59 Blocking Flows Analysis 2
1:23:23 Blocking Flows Analysis 3
1:23:49 Dinitz Analysis 1
1:24:09 Dinitz Analysis 2

Laufzeit (hh:mm:ss)

01:24:52

Serie

Algorithmen II, Vorlesung, WS 2016/17

Publiziert am

22.11.2016

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz