Reading Group Algorithms
Instructor | Sebastian Forster |
Type: | 2 SE |
ECTS: | 5 |
Curriculum: | Master Informatik |
Time and Place: | Wednesday, 12:00-13:30, Lise Meitner Hörsaal and Online (Nov 24 – Dec 15) |
Schedule
Date | Speaker | Title | Material |
---|---|---|---|
06.10. | Preliminary Meeting | ||
12.10. | Joran van Apeldoorn | What is this Quantum thing people keep talking about? | slides |
13.10. | Joran van Apeldoorn | Quantum graph algorithms | slides |
20.10. | Organizational Meeting | ||
27.10. | — | No class | |
03.11. | Discussion of Presentation Techniques | slides | |
10.11. | Maximilian Probst Gutenberg | Near-Optimal Decremental SSSP in Dense Weighted Digraphs | arXiv DOI |
16.11. | Yasamin Nazari | Distributed and Parallel Graph Distance Approximation | slides |
17.11. | Yasamin Nazari | Parallel Spanners and Distance Approximation | DOI arXiv |
24.11. | Kathrin Hanauer | Fully Dynamic Reachability – in Practice! | slides DOI arXiv |
01.12. | Tijn de Vos | Faster Cut Sparsification of Weighted Graphs | slides arXiv |
08.12. | — | Public Holiday | |
15.12. | Mara Grilnberger | Simple Label-Correcting Algorithms for Partially Dynamic Approximate Shortest Paths in Directed Graphs | slides DOI |
22.12. | — | No class | |
12.01. | Daniel Schmitt | Maintaining Triangle Queries under Updates | slides DOI arXiv |
19.01. | Antonis Skarlatos | Simple dynamic algorithms for Maximal Independent Set, Maximum Flow and Maximum Matching | slides DOI arXiv |
26.01. | Martin Grösbacher | Dynamic Matching Algorithms in Practice | slides DOI arXiv |
List of Papers
- [GK21] Simple dynamic algorithms for Maximal Independent Set, Maximum Flow and Maximum Matching
Manoj Gupta, Shahbaz Khan. In Proc. of the Symposium on Simplicity in Algorithms (SOSA), 2021
DOI arXiv - [HKPS] Dynamic Matching Algorithms in Practice
Monika Henzinger, Shahbaz Khan, Richard Paul, Christian Schulz. In Proc. of the European Symposium on Algorithms (ESA), 2020
DOI arXiv - [KNN+20] Maintaining Triangle Queries under Updates
Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, Haozhe Zhang. ACM Trans. Database Syst. 45(3): 11:1-11:46, 2020
DOI arXiv - [KL20] Simple Label-Correcting Algorithms for Partially Dynamic Approximate Shortest Paths in Directed Graphs
Adam Karczmarz, Jakub Lacki. In Proc. of the Symposium on Simplicity in Algorithms (SOSA), 2020
DOI
Companion Reports
- Mara Grilnberger: A Deterministic "Folklore" Algorithm for Decremental APSP in Weighted, Directed Graphs
- Martin Grösbacher: Fast Approximate Optimum Matching on dynamic graphs in practice
- Daniel Schmitt: Exact Dynamic Triangle Counting
- Antonis Skarlatos: Worst-case adjustment complexity for the problem of maximal independent set
- Tijn de Vos: Not-As-Fast Cut Sparsification of Weighted Graphs
Guidelines
- Talk of 45 minutes (+ 15 minutes for questions)
- Companion report of 5–10 pages
- Language: English