NPTEL : ACM Summer School on Graph Theory and Graph Algorithms (Dr. N.S. Narayanaswamy) (Special Lecture Series)

Co-ordinators : Dr. N.S. Narayanaswamy


Lecture 1 - Basic Graph theory and Graph Algorithms - Part 1

Lecture 2 - Basic Graph theory and Graph Algorithms - Part 2

Lecture 3 - Basic Graph theory and Graph Algorithms - Part 3

Lecture 4 - Basic Graph theory and Graph Algorithms - Part 4

Lecture 5 - Basic Graph theory and Graph Algorithms - Part 5

Lecture 6 - Geometric Algorithms - Part 1

Lecture 7 - Geometric Algorithms - Part 2

Lecture 8 - Geometric Algorithms - Part 3

Lecture 9 - Geometric Algorithms - Part 4

Lecture 10 - Geometric Algorithms - Part 5

Lecture 11 - Geometric Algorithms - Part 6

Lecture 12 - Introduction to Computational Complexity,P,NP classes

Lecture 13 - NPC Reductions through examples - Part 1

Lecture 14 - NPC Reductions through examples - Part 2

Lecture 15 - NPC Reductions through examples - 3SAT

Lecture 16 - Subset Sum, Knapsack

Lecture 17 - Directed Hamiltonian Path-NPC Reduction

Lecture 18 - Introduction to LPnDuality theorem

Lecture 19 - Design of Approx.algorithms using primal dual scheme - Hitting set

Lecture 20 - Approx Vertex Cover

Lecture 21 - Appox for Min Cost VC, Approx for Min cost Set Cover

Lecture 22 - 2-factor approx for metric TSP, 1.5 Approx christofides Algo

Lecture 23 - knapsack Approx, 1/2 - factor Approx, 1- ε Approx: FPTAS

Lecture 24 - Perfect graphs,weak and strong perfect graph conjecture,line graphs,interval graphs

Lecture 25 - α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture - Part 1

Lecture 26 - α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture - Part 2

Lecture 27 - Comparability graph, Permutation graphs, AT-free graphs, Trapezoidal graphs, Circular arc graphs, Boxicity and related concepts

Lecture 28 - Fixed Parameter Algorithms, -VC, Cluster vertex deletion, - Branching

Lecture 29 - Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression, Analysing branching algorithm - Part 1

Lecture 30 - Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression, Analysing branching algorithm - Part 2

Lecture 31 - Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression, Analysing branching algorithm - Part 3

Lecture 32 - Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms - Part 1

Lecture 33 - Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms - Part 2