COL751: Algorithmic Graph Theory

Evaluation: The course policy is:

• Assignments:  2 x 10 = 20%
• Exams:  33% + 35%
• Quizzes (best n-1 out of n):  12%
• Research Project (extra weightage):  20%

Passing criteria: 30% in course total

Audit-pass criteria: 45% in course total and at least 75% attendance

Acadmic Honesty: Cheating or allowing anyone to copy would lead to a penalty of one grade per assignment / quiz / exam.

Here is a tentative list of topics that will be covered in the course:

• Aysmptotic Complexity, Hitting Set
• Distance Preservers, Distance Oracles
• All-Pairs approximate distance computation
• Algorithm for computing max-flow
• Max-flow Min-cut theorem
• Structural properties of min-cuts
• k-edge Connectivity Preserver
• Gomory-Hu tree computation
• All-Pairs Bounded-min-cut algorithm
• Maximum matching in bipartite and general graphs
• Hall’s theorem, Tutte’s theorem, Gallai-Edmonds decomposition
• Arborescences and Branchings, Edmonds theorem for disjoint arborescences
• Streaming algorithms