KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Schulz, Christian; KIT | Webcast [Hrsg.]

  • 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
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 22.11.2016
Erstellungsdatum 15.11.2016
DOI 10.5445/DIVA/2016-742
Identifikator KITopen-ID: 1000114311
Lizenz KITopen-Lizenz
Serie Algorithmen II, Vorlesung, WS 2016/17
Folge 8
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page