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:

Exam:

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. 

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 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
14.05.2019Spanners II  

Announcements

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

Material