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

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

Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms ( Part -1 )

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