KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Sanders, Peter; KIT | Webcast [Hrsg.]

  • 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


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 06.11.2018
Erstellungsdatum 05.11.2018
DOI 10.5445/DIVA/2018-803
Identifikator KITopen-ID: 1000115988
Serie Algorithmen II, Vorlesung, WS 2018/19
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page