IIT Madras · Computer Science

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

33 free video lectures

33 video lectures. Topics: Basic Graph theory and Graph Algorithms Part-1; Basic Graph theory and Graph Algorithms Part-2; Basic Graph theory and Graph Algorithms Part-3; Basic Graph theory and Graph Algorithms Part-4; Basic Graph theory and Graph Algorithms Part-5; Geometric Algorithms Part-1…

▶ Play on Open Lecture HallCourse page ↗

Lectures

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

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Madras.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights