AIS - AIS Graph Theory and Graph Algorithms (2019)

Speakers and Syllabus


Graphs are ubiquitous mathematical objects used to model several fundamental combinatorial questions and algorithms. Algorithms form the core of computing. This course will cover several classical and modern topics in graph algorithms. The emphasis will be on developing problem solving skills. We will also cover topics that exhibit limitations on designing efficient algorithms (NP-completeness) and ways to cope with such limitations (including approximation algorithms and parameterized complexity).


Names and affiliation of speakers and course associates.

  1. Aritra Banik, NISER Bhubaneswar
  2. L. Sunil Chandran, IISc Bangalore
  3. K. Murali Krishnan, NIT Calicut
  4. Venkatesh Raman, IMSc Chennai
  5. N. S. Narayanaswamy, IIT Madras
  6. Jasine Babu, IIT Palakkad

 

Syllabus to be covered in terms of modules:
Module-1:

  •  Basic Graph theory and Graph Algorithms (BGA: 3 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. (3 lectures)

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 definitions and reductions through examples (2 lectures)
  • Clique, Vertex Cover, TSP, Set Cover, number problems like partition, knapsack (3 lectures)

Module-4:

  • 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. (7 lectures)

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:

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

Names of speakers:

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

Names of Course associates:

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

 

 


Time Table

  9.30 - 11.00 11.00 - 11.30 11.30 - 1.00 1.00 - 2.30 2.30 - 4.30
Date Lecture 1   Lecture 2   Tutorial
17.06.2019 NSN (BGA)   NSN (BGA)   Rani, Remi & NSN
18.06.2019 NSN (BGA)   AB (GA)   Rani, Remi & NSN
19.06.2019 NSN (BGA)   AB (GA)   Rani, Remi & NSN
20.06.2019 NSN (BGA)   AB (GA)   Rani, Remi & AB
21.06.2019 NSN (BGA)   AB (NF)   Rani, Remi & AB
22.06.2019 AB (NF)   AB (NF)   Rani, Remi & AB
23.06.2019 SUNDAY   SUNDAY   SUNDAY
24.06.2019 Murali (NPC)   Murali (NPC) L Neeta, Dhanya & Murali
25.06.2019 Murali (NPC) T Jasine (Approx) U Neeta, Dhanya & Murali
26.06.2019 Murali (NPC) E Jasine (Approx) N Neeta, Dhanya & Murali
27.06.2019 Murali (NPC) A Jasine (Approx) C Neeta, Dhanya & Jasine
28.06.2019 Murali (Approx)   Jasine (Approx) H Neeta, Dhanya & Jasine
29.06.2019 Murali (Approx)   Jasine (Approx)   Neeta & Dhanya Neeta, Dhanya & Jasine
30.06.2019 SUNDAY   SUNDAY   SUNDAY
01.07.2019 VR (PC)   Sunil (Special graphs)   Remi, Rema & VR
02.07.2019 VR (PC)   Sunil (Special graphs)   Remi, Rema & VR
03.07.2019 VR (PC)   Sunil (Special graphs)   Remi, Rema & VR
04.07.2019 VR (PC)   Sunil (Special graphs)   Remi, Rema & Sunil
05.07.2019 VR (PC)   Sunil (Special graphs)   Remi, Rema & Sunil

 

 

File Attachments: