# ACM Summer School on Graph Theory and Graph Algorithms,2019 - Calicut

- Institution: IIT Madras
- Department: Special Series
- Level: Undergraduate
- Language: English
- Subjects: Computer science
- Source: [NPTEL](https://nptel.ac.in/courses/128106008)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/128106008)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Basic Graph theory and Graph Algorithms Part-1](https://invisiblenetwork.ai/learn/nptel/128106008/8537f2eb17ab) (Video)
2. [Basic Graph theory and Graph Algorithms Part-2](https://invisiblenetwork.ai/learn/nptel/128106008/28a0d4286ccb) (Video)
3. [Basic Graph theory and Graph Algorithms Part-3](https://invisiblenetwork.ai/learn/nptel/128106008/fcf05d6bcd60) (Video)
4. [Basic Graph theory and Graph Algorithms Part-4](https://invisiblenetwork.ai/learn/nptel/128106008/e71a13c17929) (Video)
5. [Basic Graph theory and Graph Algorithms Part-5](https://invisiblenetwork.ai/learn/nptel/128106008/84ffe9dcbd4c) (Video)
6. [Geometric Algorithms Part-1](https://invisiblenetwork.ai/learn/nptel/128106008/eaab76f31f74) (Video)
7. [Geometric Algorithms Part-2](https://invisiblenetwork.ai/learn/nptel/128106008/2ab5ee5b536b) (Video)
8. [Geometric Algorithms Part-3](https://invisiblenetwork.ai/learn/nptel/128106008/b2ff9cd50381) (Video)
9. [Geometric Algorithms Part-4](https://invisiblenetwork.ai/learn/nptel/128106008/4fba0588db9e) (Video)
10. [Geometric Algorithms Part-5](https://invisiblenetwork.ai/learn/nptel/128106008/aede1668dc2b) (Video)
11. [Geometric Algorithms Part-6](https://invisiblenetwork.ai/learn/nptel/128106008/3d40807b37a6) (Video)
12. [Introduction to Computational Complexity,P,NP classes](https://invisiblenetwork.ai/learn/nptel/128106008/5846b5c965bd) (Video)
13. [NPC Reductions through examples Part-1](https://invisiblenetwork.ai/learn/nptel/128106008/b33d1c3c7fbf) (Video)
14. [NPC Reductions through examples Part-2](https://invisiblenetwork.ai/learn/nptel/128106008/001540e9ac55) (Video)
15. [NPC Reductions through examples - 3SAT](https://invisiblenetwork.ai/learn/nptel/128106008/284020d7ce38) (Video)
16. [Subset Sum, Knapsack](https://invisiblenetwork.ai/learn/nptel/128106008/eec5db47f0ca) (Video)
17. [Directed Hamiltonian Path- NPC Reduction](https://invisiblenetwork.ai/learn/nptel/128106008/dbcd7c34bbc6) (Video)
18. [Introduction to LPnDuality theorem](https://invisiblenetwork.ai/learn/nptel/128106008/6c156304ace8) (Video)
19. [Design of Approx.algorithms using primal dual scheme - Hitting set](https://invisiblenetwork.ai/learn/nptel/128106008/4a953f0f2d1b) (Video)
20. [Approx Vertex Cover](https://invisiblenetwork.ai/learn/nptel/128106008/b64031492cdc) (Video)
21. [Appox for Min Cost VC, Approx for Min cost Set Cover](https://invisiblenetwork.ai/learn/nptel/128106008/bee4cf45baab) (Video)
22. [2- factor approx for metric TSP, 1.5 Approx christofides Algo](https://invisiblenetwork.ai/learn/nptel/128106008/9c72e558ce8f) (Video)
23. [knapsack Approx, 1/2 - factor Approx, 1- ε Approx: FPTAS](https://invisiblenetwork.ai/learn/nptel/128106008/710a1efdb7bb) (Video)
24. [Perfect graphs,weak & strong perfect graph conjecture,line graphs,interval graphs](https://invisiblenetwork.ai/learn/nptel/128106008/40daa7c66153) (Video)
25. [α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture ( Part -1 )](https://invisiblenetwork.ai/learn/nptel/128106008/7fa481f18dfd) (Video)
26. [α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture ( Part -2 )](https://invisiblenetwork.ai/learn/nptel/128106008/3a67c0579f99) (Video)
27. [Comparability graph, Permutation graphs, AT-free graphs, Trapezoidal graphs, Circular arc graphs, Boxicity and related concepts](https://invisiblenetwork.ai/learn/nptel/128106008/dc9d138133f2) (Video)
28. [Fixed Parameter Algorithms, -VC, Cluster vertex deletion, - Branching](https://invisiblenetwork.ai/learn/nptel/128106008/d650699e741b) (Video)
29. [Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -1 )](https://invisiblenetwork.ai/learn/nptel/128106008/c8998933f480) (Video)
30. [Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -2 )Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm…](https://invisiblenetwork.ai/learn/nptel/128106008/cb51c42d606c) (Video)
31. [Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -3 )](https://invisiblenetwork.ai/learn/nptel/128106008/37bc50b527fb) (Video)
32. [Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms ( Part -1 )](https://invisiblenetwork.ai/learn/nptel/128106008/4029fbcc52be) (Video)
33. [Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms ( Part -2 )](https://invisiblenetwork.ai/learn/nptel/128106008/661c3efd1ad0) (Video)