Algorithmen II, Vorlesung, WS 2016/17, 15.11.2016, 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
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 22.11.2016 |
| Erstellungsdatum | 15.11.2016 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2016-742 |
| Identifikator | KITopen-ID: 1000114311 |
| Lizenz | KITopen-Lizenz |
| Serie | Algorithmen II, Vorlesung, WS 2016/17 |
| Folge | 8 |