Dynamic Graph Algorithms

This is an elective course meant for M.Sc students and third year B.Sc students.

Instructors:

Pranabendu Misra, Samir Datta, Prajakta Nimbhorkar


Lectures

Topics covered so far (there are two lectures on each Friday):

  1. Aug 9 [PM]: Introduction to dynamic algorithms, dynamic connectivity in forests
  2. Aug 16[PM]: Dynamic connectivity in general graphs using layered forests (Ref: this paper and these and these slides for the two lectures)
  3. Aug 16[PN]: Splay trees and their amortized analysis (Ref: this, this Also see this for motivation and example)
  4. Aug 23[PN]: Dynamic minimum spanning trees under decremental updates (Reference
  5. Aug 23[SD]: Parallel dynamic algorithms: Parallel computation model CRCW PRAM, connectivity in log n time, MST in O(1) time
  6. Aug 30[SD]: Batch updates for connectivity in the parallel setting
  7. Aug 30[PM]: Introduction to top trees
  8. Sept 6[PM]: Top trees continued
  9. Sept 13[SD]: Reachability in dynamic setting in parallel model
  10. Sept 20[SD]: Batch updates for reachability in parallel model
  11. Sept 20[PN]: Fully dynamic MST