IIT Gandhinagar, IMSC · Computer Science
Parameterized Algorithms
Prof. Neeldhara Misra, Prof. Saket Saurabh · 50 free video lectures
This is a first course on techniques in parameterized algorithms, a paradigm of algorithm design that analyzes running time in finer detail than classical complexity theory: instead of expressing the running time as a function of the input size only, dependence on one or more parameters of the…
▶ Play on Open Lecture HallCourse page ↗
Lectures
- Invitation to FPT
- Formalizing FPT
- Kernelization: High Degree Rule
- Kernelization: d-Hitting Set
- Kernelization: Crown Reduciton
- Kernelization: Nemhauser-Trotter and Expansion Lemma
- Introduction to Branching
- Analyzing Recurrences
- High-Degree Branching for FVS
- Vertex Cover above LP
- Applications of Vertex Cover above Matching
- Iterative Compression I: Setting Up the Method
- Iterative Compression II: Vertex Cover and Tournament Feedback Vertex Set
- Iterative Compression III: Feedback Vertex Set and 3-Hitting Set
- Iterative Compression IV: Odd Cycle Transversal
- Introduction to Randomized Algorithms via a Simple Randomized FPT Algorithm for FVS
- Color Coding for Longest Path
- Chromatic Coding for Feedback Arc Set on Tournaments
- Random Separation and Subgraph Isomorphism
- Derandomization
- Divide and Conquer and Separator
- Towards Defining Treewidth
- Treewidth and Constructing Treedecomposition of Few Graph Classes
- Structural Properties of Treedecomposition and Win-Win
- Nice Tree Decomposition and Algorithm for Max Weight Independent Set
- Dynamic Programming Algorithm over graphs of Bounded Treewidth
- FPT Appproximation Algorithm for Computing Tree Decomposition - Part 01
- FPT Appproximation Algorithm for Computing Tree Decomposition - Part 02
- FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 01
- FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 02
- Dynamic Programming Over Subsets for Set Cover
- Dynamic Programming Over Subsets for Steiner Tree
- ILP for Envy-Free Allocations and Lobbying
- ILP for Imbalance Parameterized by Vertex Cover
- Important Cuts: Basic
- Important Cuts: Enumeration and Bounds
- FPT Algorithm for Multiway Cut
- FPT Algorithm for Directed Feedback Edge Set
- Algebraic Techniques: Inclusion Exclusion (Coloring)
- Algebraic Techniques: Inclusion Exclusion (Hamiltonian Path)
- Algebraic Techniques: Matrix Multiplication
- Algebraic Techniques: Polynomial Method
- Matroids: Representative Sets
- Matroids: Representative Sets -- Computation and Combinatorics
- Matroids: Representative Sets -- Applications (Paths and Kernels)
- Matroids: Representative Sets -- Applications (Directed Long Cycle)
- Reductions --- An Introduction
- Reductions --- Problems as Hard as Clique I (Clique on Regular Graphs)
- Reductions --- Problems as Hard as Clique (PVC, MCC, MIS)
- Reductions --- Problems as Hard as Clique (Dominating Set, Set Cover)
From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Gandhinagar, IMSC.
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