Distributed and Sequential Graph Algorithms

Advanced Course, 2+1

Basic Information


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



There will be oral exams at the end of the semenster.

Mailing ListPlease subscribe here: https://lists.mpi-inf.mpg.de/listinfo/algorithms
Prerequisites:Basic knowledge of algorithms, graph theory and probability will be assumed. 


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 




Date TopicReferencesHomework
09.04.2019Minimum Dominating SetMinimum Dominating Set (Sec 7.1) Sheet 1
16.04.2019Low Diameter Decomposition INetwork Decomposition (Sec 1.5)  Sheet 2
23.04.2019Low Diameter Decomposition IISequential and Randomized Construction  No Exercise Sheet
30.04.2019Spanners IGraph SpannersSheet 3
07.05.2019Distributed ColoringLecture NotesSheet 4
21.05.2019Spanners IILecture NotesSheet 5
28.05.2019Introduction to LLL Lecture Notes (See Chapter 2)No Exercises
04.06.2019LLLLecture Notes (also see the references)Sheet 6
11.06.2019Deterministic Network DecompositionLecture NotesSheet 8
18.06.2019Graph Connectivity I: Sequential AlgorithmsKargar's Mincut Algorithm
Minimum k-Connected Subgraph
Sheet 9 (Preliminary)
25.06.2019Graph Connectivity II: Distributed AlgorithmsLecture NotesNo Homework
02.07.2019Distributed Algorithms for All Pairs Shortest PathsDistributed RoutingNo Homework


  1. Please subscribe to our Mailing List: https://lists.mpi-inf.mpg.de/listinfo/algorithms