Compact Graph Data-Structures

Special Topics in Algorithms (COL 866)

Course Information

Instructor: Keerti Choudhary

Time: Monday / Thursday 2:00-3:30 PM (Slot AA)

Prerequisites: Data Structures and Algorithms (COL 106) or equivalent, Basics of Probability and Statistics.
Analysis and Design of Algorithms (COL 351) is recommended, but not mandatory.

Evaluation: The course evaluation policy is: 25% project (group size 1-2); 10% class participation; 40% assignments (best 4 out of 5); and 25% announced-quizzes and/or major-exam.

Syllabus

In this course, we will cover various data structure problems for efficiently solving reachability, connectivity, exact/approximate distances, min-cuts, and other related questions, in static, dynamic, and fault-tolerant scenario.

The following is a tentative list of topics to be covered in the course.

  • Incremental and Decremental Shortest-Path-Tree Algorithms
  • Dynamic Depth First Search, Connectivity, and Reachability Structures
  • Fault-tolerant Connectivity and Reachability Structures
  • Graph Spanners, Greedy Construction, Girth Conjecture
  • Clustering approach to efficient Spanner Computation
  • Throup and Zwick Distance Oracle
  • Additive Spanners
  • Dynamic and Fault-tolerant Spanners
  • Diameter and Eccentricity Spanners

Lectures


S. No. Date Topic
01 04 February Distance Spanners (for Undirected Graphs) Lecture Notes
02 08 February Hitting Sets and Additive Spanners Lecture Notes
03 11 February Distance Oracle (Introduction to hierarchical construction) Lecture Notes
04 15 February Fault-tolerant Spanners (Randomized construction) Lecture Notes
05 18 February Chernoff Bound + Level Ancestor Problem Lecture Notes
06 22 February Fault-tolerant BFS Trees 1-FT-BFS construction  Lecture Notes
07 25 February Fault-tolerant BFS Trees (contd.) Lecture Notes
08 01 March 1-FT Subset Distance Oracle + k-FT connectivity preserver 1-FT Distance Oracle  k-FT connectivity preserver
09 04 March Incremental Shortest Paths Incremental SSSP  Lecture Notes
10 08 March Decremental Shortest Paths Decremental SSSP  Lecture Notes
11 11 March Partially Dynamic (1+eps)-Approximate Distances Lecture Notes
12 20 March Modular arithmetic and Fully-dynamic All Pairs Reachability in DAGs Lecture Notes
13 22 March Rectangular-matrix-multiplication and Fully-dynamic All Pairs Reachability in DAGs Lecture Notes
14 25 March Fully-dynamic Connectivity in Trees Lecture Notes
15 01 April Fully-dynamic Connectivity in General Graphs
16 08 April Partially Dynamic Algorithms for Strong Connectivity Lecture Notes
17 10 April Decremental All Pairs Reachability in General Digraphs
18 12 April Approximation of Graph Eccentricities Lecture Notes
19 15 April Eccentricity Spanner of stretch two Lecture Notes
20 19 April Diameter Spanner and Diameter Approximation Lecture Notes
21 22 April Major Presentation
22 26 April Major Presentation
23 29 April Major Presentation + LCA data structure Lecture Notes