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

Lecture 12 of 33ACM Summer School on Graph Theory and Graph Algorithms

Introduction to Computational Complexity,P,NP classes

IIT Madras

Credits and licence

From
ACM Summer School on Graph Theory and Graph Algorithms,2019 - Calicut, IIT Madras (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  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