# Basic Information

Lectures: Tuesday, 10:15-12:00,  E1.4 024 Saeed Amiri and Pranabendu Misra April 9, 2019 Friday 26.04 ; Monday 29.04 and then every 2 weeks on Friday Cosmina Croitoru 26.04 16-18 5 There will be oral exams at the end of the semenster. Please subscribe here: https://lists.mpi-inf.mpg.de/listinfo/algorithms 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 AlgorithmMinimum 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

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