Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Neeldhara Misra
NPTEL Co-ordinating Institute : IIT Gandhinagar, IMSC
NPTEL Lecture Count : 50
NPTEL Course Size : 5.3 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
Lecture 1 - Invitation to FPT
Lecture 2 - Formalizing FPT
Lecture 3 - Kernelization: High Degree Rule
Lecture 4 - Kernelization: d-Hitting Set
Lecture 5 - Kernelization: Crown Reduciton
Lecture 6 - Kernelization: Nemhauser-Trotter and Expansion Lemma
Lecture 7 - Introduction to Branching
Lecture 8 - Analyzing Recurrences
Lecture 9 - High-Degree Branching for FVS
Lecture 10 - Vertex Cover above LP
Lecture 11 - Applications of Vertex Cover above Matching
Lecture 12 - Iterative Compression I: Setting Up the Method
Lecture 13 - Iterative Compression II: Vertex Cover and Tournament Feedback Vertex Set
Lecture 14 - Iterative Compression III: Feedback Vertex Set and 3-Hitting Set
Lecture 15 - Iterative Compression IV: Odd Cycle Transversal
Lecture 16 - Introduction to Randomized Algorithms via a Simple Randomized FPT Algorithm for FVS
Lecture 17 - Color Coding for Longest Path
Lecture 18 - Chromatic Coding for Feedback Arc Set on Tournaments
Lecture 19 - Random Separation and Subgraph Isomorphism
Lecture 20 - Derandomization
Lecture 21 - Divide and Conquer and Separator
Lecture 22 - Towards Defining Treewidth
Lecture 23 - Treewidth and Constructing Treedecomposition of Few Graph Classes
Lecture 24 - Structural Properties of Treedecomposition and Win-Win
Lecture 25 - Nice Tree Decomposition and Algorithm for Max Weight Independent Set
Lecture 26 - Dynamic Programming Algorithm over graphs of Bounded Treewidth
Lecture 27 - FPT Appproximation Algorithm for Computing Tree Decomposition - Part 1
Lecture 28 - FPT Appproximation Algorithm for Computing Tree Decomposition - Part 2
Lecture 29 - FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 1
Lecture 30 - FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 2
Lecture 31 - Dynamic Programming Over Subsets for Set Cover
Lecture 32 - Dynamic Programming Over Subsets for Steiner Tree
Lecture 33 - ILP for Envy-Free Allocations and Lobbying
Lecture 34 - ILP for Imbalance Parameterized by Vertex Cover
Lecture 35 - Important Cuts: Basic
Lecture 36 - Important Cuts: Enumeration and Bounds
Lecture 37 - FPT Algorithm for Multiway Cut
Lecture 38 - FPT Algorithm for Directed Feedback Edge Set
Lecture 39 - Algebraic Techniques: Inclusion Exclusion (Coloring)
Lecture 40 - Algebraic Techniques: Inclusion Exclusion (Hamiltonian Path)
Lecture 41 - Algebraic Techniques: Matrix Multiplication
Lecture 42 - Algebraic Techniques: Polynomial Method
Lecture 43 - Matroids: Representative Sets
Lecture 44 - Matroids: Representative Sets - Computation and Combinatorics
Lecture 45 - Matroids: Representative Sets - Applications (Paths and Kernels)
Lecture 46 - Matroids: Representative Sets - Applications (Directed Long Cycle)
Lecture 47 - Reductions - An Introduction
Lecture 48 - Reductions - Problems as Hard as Clique I (Clique on Regular Graphs)
Lecture 49 - Reductions - Problems as Hard as Clique (PVC, MCC, MIS)
Lecture 50 - Reductions - Problems as Hard as Clique (Dominating Set, Set Cover)