Succinct Graph Structures and Their Applications S2020

Lecture Time & Place: Thursday 10:15-12:00, Ziskind 155 Zoom link
TA: Avi Cohen
Prerequisite: Sufficient comfort with both algorithm design & analysis.

Home Exam (due midnight of Aug. 5)

Course Schedule:

(23/04) Lecture  01: Graph Spanners, Greedy Construction, Girth Conjecture, and
3-spanner Algorithm by Baswana-Sen. Slides  Notes-2018​​​​​​ Exercise-01 due May 27

(30/04) Lecture  02: Additive and Nearly-Additive Spanners. Slides Notes-2018

(07/05) Lecture  03: Distance Oracles. Slides Notes-2018

(14/05) Lecture  04: Routing Schemes.  Slides Notes-2018

(21/05) Lecture  05: Labeling Schemes. Slides  Notes-2018

(28/05) No Class (Shavuot) Exercise-02 due June 14

(04/06) Lecture  06:  Probablistic Tree Embedding (FRT)  Slides Notes-2018

(11/06) Lecture  07: Cut Sparsifiers Slides Notes-2018 Exercise-03 due June 28

(18/06) Lecture  08:  Efficienct Min-Cut Computation Slides

(25/06) Lecture  9:  Succinct Cut Representation (Gomory Hu) Slides

  • Lecture 9 of Richard Peng (CS7510 Graph Algorithms, Georgia Institute of Technology, Fall 2019)
  • Lecture 6 of Chandra Chekuri (CS 598: Topics in Combinatorial Optimization, UIUC,  Fall 2010)

(02/07) Lecture  10:  Fault-Tolerant Graph Structure I: FT-BFS Structures
Notes-'20 Slides-'13 Exercise-04 due July 16

(09/07) No Class (Seventeenth of Tammuz Fast)

(16/07) Lecture  11:  Fault-Tolerant Graph Structure II:  Distance Sensitivity Oracles and Fault Tolerant Spanners. Notes-2018 Notes-2020


Useful Probabilities Inequalities: Handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring'11).