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
- 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
- Geometric Algorithms Part-2
- Geometric Algorithms Part-3
- Geometric Algorithms Part-4
- Geometric Algorithms Part-5
- Geometric Algorithms Part-6
- Introduction to Computational Complexity,P,NP classes
- NPC Reductions through examples Part-1
- NPC Reductions through examples Part-2
- NPC Reductions through examples - 3SAT
- Subset Sum, Knapsack
- Directed Hamiltonian Path- NPC Reduction
- Introduction to LPnDuality theorem
- Design of Approx.algorithms using primal dual scheme - Hitting set
- Approx Vertex Cover
- Appox for Min Cost VC, Approx for Min cost Set Cover
- 2- factor approx for metric TSP, 1.5 Approx christofides Algo
- knapsack Approx, 1/2 - factor Approx, 1- ε Approx: FPTAS
- Perfect graphs,weak & strong perfect graph conjecture,line graphs,interval graphs
- α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture ( Part -1 )
- α perfection of interval graphs,chordal graphs,expansion lemma, proof for weak perfect conjecture ( Part -2 )
- Comparability graph, Permutation graphs, AT-free graphs, Trapezoidal graphs, Circular arc graphs, Boxicity and related concepts
- Fixed Parameter Algorithms, -VC, Cluster vertex deletion, - Branching
- Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -1 )
- Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -2 )Kernelization,…
- Kernelization, -VC, CrownDecomposition, Feedback vertex set, Herative compression , Analysing branching algorithm ( Part -3 )
- Hardness in Parameterized Complexity - W - hard reductions Exponential algorithms ( Part -1 )
- 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