07: Algorithmen II, Vorlesung, WS 2018/19, 05.11.2018

An episode of the Algorithmen 2, Vorlesung, WS18/19 podcast, hosted by Prof. Dr. Peter Sanders, titled "07: Algorithmen II, Vorlesung, WS 2018/19, 05.11.2018" was published on November 6, 2018 and runs 86 minutes.

November 6, 2018 ·86m · Algorithmen 2, Vorlesung, WS18/19

Summary

07 | 0:00:00 Start 0:00:37 Tiefensuchschema 0:01:14 Starke Zusammenhangskomponenten 0:02:21 Schrumpfgraph 0:02:55 Konkreter: SCCs mittels DFS 0:04:04 Invarianten von G 0:05:58 Lemma: Abgeschlossene SCCs von G sind SCCs von G 0:06:14 Repräsentation offener Komponenten 0:13:24 Beispiel 0:24:48 Zusammenfassung: SCC Berechnung 0:26:22 2-zusammenhängende Komponenten 0:29:06 Mehr DFS-basierte Linearzeitalgorithmen 0:31:56 Maximum Flows and Matching 0:33:06 Definitions: Network 0:34:38 Definition: Flows 0:36:14 Definition: Minimum s-t Cuts 0:37:22 Duality between flows and cuts 0:40:17 Applications 0:47:18 Applications in our group 0:54:42 Option 1: Linear programming 0:57:56 Algorithms 1956 - now 1:06:42 Augmenting paths 1:09:13 Example 1:13:33 Residual Graph 1:19:05 Ford Fulkerson Algorithm 1:21:39 A bad example for Ford Fulkerson 1:22:56 An even worse example 1:20:25 Average case Analyse für MST

Episode Description