Completed
Branchable Vertex
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Independent Set on P_k-Free Graphs in Quasi-Polynomial Time
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Problem Definition
- 3 Independent Set One of Karp's 21 NP-complete problems
- 4 Independent Set is Hard
- 5 Known Polynomial Time classes
- 6 Known Results Beyond polyomial time
- 7 Our Results
- 8 All remaining cases in P?
- 9 Algorithm in a nutshell
- 10 Running time?
- 11 Balanced Separator Lemma
- 12 How to achieve goal?
- 13 Collecting Balanced Separators
- 14 Actual Algorithm
- 15 (Not So) Updated Goal
- 16 Branchable Vertex
- 17 Main Lemma
- 18 Upper bound on level sets
- 19 Putting it Together
