Distributed and Sequential Graph Algorithms
Advanced Course, 2+1
Basic Information
Lectures: | Tuesday, 10:15-12:00, E1.4 024 |
|---|---|
| Lecturers: | Saeed Amiri and Pranabendu Misra |
| First lecture: | April 9, 2019 |
| Tutorials: | Friday 26.04 ; Monday 29.04 and then every 2 weeks on Friday |
| Assistant: | Cosmina Croitoru |
First tutorial: | 26.04 16-18 |
| Credits: | 5 |
Exam: | There will be oral exams at the end of the semenster. |
| Mailing List | Please subscribe here: https://lists.mpi-inf.mpg.de/listinfo/algorithms |
| Prerequisites: | Basic knowledge of algorithms, graph theory and probability will be assumed. |
Description
In this course we study distributed and sequential algorithms for several graph theory problems. These problems, which are abstractions of various real world problems, are well studied in computer science. The aim of this course is to understand the challenges that arise in solving these problems in the above settings, and the techniques and methods to solve them.
The plan(tentative) is to study sequential and distributed algorithms for the following:
- Minimum Dominating Set approximation
- Low Diameter Decomposition of graphs and applications
- Max Cut approximation
- Approximate Minimum 2-Edge Connected Subgraph
- Maximum Matching approximation
- Low stretch Spanners
- Lovasz Local Lemma
Schedule
Lectures
| Date | Topic | References | Homework |
|---|---|---|---|
| 09.04.2019 | Minimum Dominating Set | Minimum Dominating Set (Sec 7.1) | Sheet 1 |
| 16.04.2019 | Low Diameter Decomposition I | Network Decomposition (Sec 1.5) | Sheet 2 |
| 23.04.2019 | Low Diameter Decomposition II | Sequential and Randomized Construction | No Exercise Sheet |
| 30.04.2019 | Spanners I | Graph Spanners | Sheet 3 |
| 07.05.2019 | Distributed Coloring | Lecture Notes | Sheet 4 |
| 21.05.2019 | Spanners II | Lecture Notes | Sheet 5 |
| 28.05.2019 | Introduction to LLL | Lecture Notes (See Chapter 2) | No Exercises |
| 04.06.2019 | LLL | Lecture Notes (also see the references) | Sheet 6 |
| 11.06.2019 | Deterministic Network Decomposition | Lecture Notes | Sheet 8 |
| 18.06.2019 | Graph Connectivity I: Sequential Algorithms | Kargar's Mincut Algorithm Minimum k-Connected Subgraph | Sheet 9 (Preliminary) |
| 25.06.2019 | Graph Connectivity II: Distributed Algorithms | Lecture Notes | No Homework |
| 02.07.2019 | Distributed Algorithms for All Pairs Shortest Paths | Distributed Routing | No Homework |
Announcements
- Please subscribe to our Mailing List: https://lists.mpi-inf.mpg.de/listinfo/algorithms
Material
- Monograph on Distrubuted Coloring by Barenboim and Elkin, 2013 https://www.cs.bgu.ac.il/~elkinm/BarenboimElkin-monograph.pdf