Summer School on Graph Theory and Graph Algorithms

Schedule

9:30-11:00 11:00-11:30 11:30-01:00 01:00-02:00 02:00-03:15 03:15-03:30 03:30-04:45
Date Lecture 1 Lecture 2 Tutorial 1 Tutorial 2
17-06-2019 Inauguration Tea NSN(BGA) Lunch NSN(BGA) Tea Rani, Rema & NSN
18-06-2019 NSN(BGA) AB(GA) Rani, Rema & NSN Rani, Rema & NSN
19-06-2019 NSN(BGA) AB(GA) Rani, Rema & NSN Rani, Rema & NSN
20-06-2019 NSN(BGA) AB(GA) Rema, Remi & AB Rema, Remi & AB
21-06-2019 NSN(BGA) AB(NF) Rema, Remi & AB Rema, Remi & AB
22-06-2019 AB(NF) AB(NF) Rema, Remi & AB Rema, Remi & AB
23-06-2019 Sunday
24-06-2019 Murali(NPC) Tea Murali(NPC) Lunch Remi, Dhanya and Murali Tea Remi, Dhanya and Murali
25-06-2019 Murali(NPC) Murali(NPC) Remi, Dhanya and Murali Remi, Dhanya and Murali
26-06-2019 Murali(NPC) Jasine(Approx) Remi, Dhanya and Murali Remi, Dhanya and Murali
27-06-2019 Murali(NPC) Jasine(Approx) Rani, Dhanya and Jasine Rani, Dhanya and Jasine
28-06-2019 Murali(Approx) Jasine(Approx) Rani, Dhanya and Jasine Rani, Dhanya and Jasine
29-06-2019 Murali(Approx) Jasine(Approx) Rani, Dhanya and Jasine Rani, Dhanya and Jasine
30-06-2019 Sunday
01-07-2019 Murali(NPC-Conclusion) Tea Sunil(Special Graphs) Lunch Rani, Rema and Sunil Tea Rani, Rema and Sunil
02-07-2019 Sunil(Special Graphs) Sunil(Special Graphs) Rani, Rema and Sunil Rani, Rema and Sunil
03-07-2019 Sunil(Special Graphs) VR(PC) Remi, Dhanya and VR Remi, Dhanya and VR
04-07-2019 VR(PC) VR(PC) Remi, Dhanya and VR Remi, Dhanya and VR
05-07-2019 VR(PC) VR(PC) Remi, Dhanya and VR Remi, Dhanya and VR

Names of Speakers

  1. Dr. Aritra Banik (AB), NISER Bhubaneshwar
  2. Dr. Jasine Babu (Jasine), IIT Palakkad
  3. Dr. L Sunil Chandran (Sunil), IISc Bangalore
  4. Dr. Muralikrishnan K (Murali), NIT Calicut
  5. Dr. N S Narayanaswamy (NSN), IIT Madras
  6. Dr. Venkatesh Raman (VR), IMSc Chennai

Names of Course Associates

  1. Ms. Dhanyamol Antony (Dhanya), NIT Calicut
  2. Ms. Rani M R (Rani), NIT Calicut
  3. Ms. Rema M (Rema), NIT Calicut
  4. Ms. Remi Raman (Remi), NIT Calicut

Syllabus

Module-1:

Basic Graph theory and Graph Algorithms (BGA: 5 lectures): Degree sequence, Havel Hakimi theorem etc Graph representations,
BFS and applications DFS and applications Algorithms on Weighted Graphs (Shortest Paths, Minimum Spanning Trees) including
correctness proofs and implementation details using data structures.

Module-2:

Geometric Algorithms (GA: 3 lectures): Convex Hull, Voronoi Diagram, Algorithm for Closest point in 2D
Network Flows (NF: 3 lectures): Max-Flow Min Cut theorem, Ford-Fulkerson Algorithms, Applications and faster algorithms

Module-3:

NP-Completeness (NPC: 5 lectures): NP-completeness definitions and reductions through examples - Clique, Vertex Cover, TSP,
Set Cover, number problems like partition, knapsack

Module-4:

Approximation Algorithms (Approx: 7 lectures): Approximation algorithms for vertex cover, steiner tree, triangle TSP, maxcut, maxsat,
knapsack, set cover including various types of approximation algorithms like PTAS, FPTAS and linear program based techniques.

Module 5:

Parameterized Algorithms (PC: 5 lectures) Algorithms using branching, kernelization, iterative compression Treewidth and
related concepts and algorithms using them, parameterized hardness

Module 6:

Special Graphs (5 lectures): Algorithms on special graph classes including in chordal, interval, comparability and perfect graphs
Boxicity and related concepts.