# 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

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: