KIT | KIT-Bibliothek | Impressum | Datenschutz

10: Parallele Algorithmen, Vorlesung, WS 2017/18, 08.01.2018

Axtmann, Michael; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:10 Minimum Spannung Trees
  • 0:03:06 Selecting and Discarding MST Edges
  • 0:09:01 Kruskal's Algorithm
  • 0:12:41 Edge Contraction
  • 0:16:29 Finding lightest incident edges
  • 0:24:06 Structure of Resulting Components
  • 0:28:51 Pseudotrees -> Rooted Trees
  • 0:31:07 Rooted Trees -> Rooted Stars by Doubling
  • 0:32:43 Contraction
  • 0:42:36 Recursion
  • 0:45:21 Analysis
  • 0:52:10 Randomized Linear Time Algorithm
  • 0:55:08 Parallel Filter Kruskal
  • 1:05:43 Running Time: Random graph with 2^16 nodes
  • 1:09:12 More on Parallel MST
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 11.01.2018
Erstellungsdatum 08.01.2018
DOI 10.5445/DIVA/2018-12
Identifikator KITopen-ID: 1000115231
Serie 10
Serie Parallele Algorithmen, Vorlesung, WS 2017/18
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page