10: Parallele Algorithmen, Vorlesung, WS 2017/18, 08.01.2018
- 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
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 11.01.2018 |
| Erstellungsdatum | 08.01.2018 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2018-12 |
| Identifikator | KITopen-ID: 1000115231 |
| Lizenz | KITopen-Lizenz |
| Serie | Parallele Algorithmen, Vorlesung, WS 2017/18 |
| Folge | 10 |