ACM Summer School on Graph Theory and Graph Algorithms - 2019 (USB)

Media Storage Type : 32 GB USB Stick

NPTEL Subject Matter Expert : Dr. N.S. Narayanaswamy

NPTEL Co-ordinating Institute : IIT Madras

NPTEL Lecture Count : 33

NPTEL Course Size : 21 GB

NPTEL PDF Text Transcription : Available and Included

NPTEL Subtitle Transcription : Available and Included (SRT)

Lecture Titles:

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