Models For Distributed Graph Computations. Algorithms and Lower Bounds For Global Problems, Such As Constructing a Bfs Tree and an Mst. Algorithms and Lower Bounds For Local Problems, Such As Coloring And Finding an Mis. Spanner Constructions and Applications. Computing In Dynamic Graphs, Computing With Advice, Approximation Algorithms And Additional Optional Related Topics. Learning Outcomes# By The End of The Course The Student Will# 1. Know Various Models For Distributed Graph Computations and Their Importance. 2. Know How to Design and Analyze Global Algorithms Under Bandwidth Restrictions. 3. Know How to Design and Analyze Local Algorithms. 4. Know Methods For Obtaining Lower Bounds.

Faculty: Computer Science
|Undergraduate Studies |Graduate Studies

Pre-required courses

(94412 - Probability (advanced) and 234247 - Algorithms 1)

Parallel course

236343 - Theory of Computation

Semestrial Information