Learn · NPTEL

Course12810600833 lectures

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

IIT Madras

Start with lecture 1 At NPTEL

Lectures

ACM Summer School on Graph Theory and Graph Algorithms

  1. Basic Graph theory and Graph Algorithms Part-1 Video
  2. Basic Graph theory and Graph Algorithms Part-2 Video
  3. Basic Graph theory and Graph Algorithms Part-3 Video
  4. Basic Graph theory and Graph Algorithms Part-4 Video
  5. Basic Graph theory and Graph Algorithms Part-5 Video
  6. Geometric Algorithms Part-1 Video
  7. Geometric Algorithms Part-2 Video
  8. Geometric Algorithms Part-3 Video
  9. Geometric Algorithms Part-4 Video
  10. Geometric Algorithms Part-5 Video
  11. Geometric Algorithms Part-6 Video
  12. Introduction to Computational Complexity,P,NP classes Video
  13. NPC Reductions through examples Part-1 Video
  14. NPC Reductions through examples Part-2 Video
  15. NPC Reductions through examples - 3SAT Video
  16. Subset Sum, Knapsack Video
  17. Directed Hamiltonian Path- NPC Reduction Video
  18. Introduction to LPnDuality theorem Video
  19. Design of Approx.algorithms using primal dual scheme - Hitting set Video
  20. Approx Vertex Cover Video
  21. Appox for Min Cost VC, Approx for Min cost Set Cover Video
  22. 2- factor approx for metric TSP, 1.5 Approx christofides Algo Video
  23. knapsack Approx, 1/2 - factor Approx, 1- ε Approx: FPTAS Video
  24. Perfect graphs,weak & strong perfect graph conjecture,line graphs,interval graphs Video
  25. α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture ( Part -1 ) Video
  26. α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture ( Part -2 ) Video
  27. Comparability graph, Permutation graphs, AT-free graphs, Trapezoidal graphs, Circular arc graphs, Boxicity and related concepts Video
  28. Fixed Parameter Algorithms, -VC, Cluster vertex deletion, - Branching Video
  29. Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -1 ) 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… Video
  31. Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -3 ) Video
  32. Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms ( Part -1 ) Video
  33. Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms ( Part -2 ) Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Madras
Department
Special Series
Level
Undergraduate
Language
English
Subjects
Computer science
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed