CSL851: Algorithmic Graph Theory

ReferenceTexts
Graph Theory by Reinhard Diestel (Chapters 1,2,3,4,5,12)
Advanced Graph Algorithms by T.Kloks
A course in Combinatorial Optimization by Alexander Schrijver
Lecture Notes
Graphs and Algorithms, Nikhil Bansal, TU Eindhoven
Topics in Combinatorial Optimization, Michel Goemans, MIT Open Courseware
Topics in Combinatorial Optimization, Chandra Chekuri, U. of Illinois
Graph Theoretic Algorithms, Therese Biedl, U of Waterloo
Advanced Topics in Graph Algorithms, Ron Shamir, Tel Aviv U.




Lecture Date
Contents
Additional reading material
Lecture notes from this course
July 24, 29, 31
Matching: Tutte-Berge Formula, Gallai-Edmonds Decomposition, Blossoms, Edmonds' Cardinality Algorithm and Proofs of Tutte-Berge Formulas and Gallai-Edmonds Decomposition,
Notes
Suyash Roongta,
Anup Bhatacharya, Khaleeque Ansari
August 5,7, 12
Weighted bipartite matching, Edmonds Algorithm for Weighted Non-Bipartite Matching,T-joins and applications
Utkarsh Ohm, Ankit Anand, Shubham Gupta
August 14, 19, 21, 26
 Factor-Critical Graphs, Ear Decompositions, Graph orientations, Splitting Off, $k$-Connectivity Orientations and Augmentations, Arborescences and Branchings
Komal Bansal, Aarti Soni, MSK Swaroop, Abhinav Kumar
Sept 4, 10
Basic Probability

Nikhil Kumar, Yashoteja Prabhu
Sep 11
Hoeffdings inequality and introduction to G(n,p)

Ashish Gaurav
Sept 16, 23, 24
Threshold for connectedness in random graphs

Siddharth Bora, Devashish Tyagi, Abhishek Gupta
Oct 9, 14
Interval Graphs, Chordal Graphs
Slides Apoorv Garg, Keshav Choudhary
Oct 28, 30
Perfect Graphs, Comparabaility graphs

Arpit Jain, Debjyoti Saharoy
Nov 4, 11, 13
Treewidth, Planar GraphsSlides Jatin Batra, Jwala rao, Sushant Saxena
Nov 18
Planar Separator Theorem
Prerequisites, Separators Ashesh
Nov 20
Expanders

Davis Isaac

Kuratowski's Theorem Slides




Course Evaluation
The course is in 3 parts with an exam (30 marks) at the end of each part. The lecture scribe is for 10 marks. Click here to download the latex template for the lecture notes. You can find your marks here


Scribe Schedule
Please click here to enter your choice for the lecture you want to scribe.