Lecture: Efficient Graph Algorithms

Lecture recording 1

• 

  dial 01

Lecture recording 2

• 

  Dijkstra bidirectional Idee

• 

  Dijkstra bidirectional Korrektheit

• 

  Dijkstra goaloriented Details

• 

  Dijkstra goaloriented Idee

• 

  Dijkstra goaloriented Korrektheit

Lecture recording 3

• 

  BFS Queue

• 

  DFS lax-kleinst

• 

  DFS lexikographische Knotenreihung

• 

  nichtlexikographische Ausgabereihung

• 

  DFS Rueckwaertsgehen

• 

  Murmelbeweis

Lecture recording 4

• 

  starke Zusammenhangskomponenten

Lecture recording 5

• 

  Artikulationspunkt

• 

  Bruecke

• 

  DFS 2-fache Zshkomp 1

• 

  DFS 2-fache Zshkomp 2

• 

  DFS 2-fache Zshkomp 3

• 

  DFS 2-fache Zshkomp 4

• 

  DFS 2-fache Zshkomp 5

• 

  Euler-Algo schematisch

• 

  Haus vom Nikolaus 1

• 

  Haus vom Nikolaus 2

• 

  Haus vom Nikolaus 3

Lecture recording 6

• 

  Branching Terminologie

• 

  Branching Zykelschrumpfung

• 

  Euler-Algo Beweis

• 

  max-flow multi-source multi-target

Lecture recording 7

• 

  Branching Beweis 1

• 

  Branching Beweis 2

• 

  Branching falsches Beispiel

Lecture recording 8

• 

  anti-symmetric

• 

  Cut 1

• 

  Cut 2

• 

  Cut 3

• 

  neuer augmentierender Pfad Bsp

• 

  neuer augmentierender Pfad einfach

Lecture recording 9

• 

  Ahuha-Orlin Beweis

• 

  Complexity Edmonds-Karp

• 

  neuer augmentierender Pfad komplex

• 

  residual network 1

• 

  residual network 2

Lecture recording 10

• 

  three indians

• 

  valid distance labeling

Lecture recording 11

• 

  saturierter Schnitt

Lecture recording 12

• 

  negative Kostenfaktoren Beispiel

• 

  negative Kostenfaktoren konzeptionell

• 

  negative Zykel Rechnung

• 

  negativer Zykel Skizze

Lecture recording 13

• 

  negative cycle initialization

• 

  succ shortest paths no neg clcly general

• 

  succ shortest paths no neg cylce simple

• 

  successive shortest paths iteration