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 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 Graphs | Slides | 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. |