Completed
Reduction from CAP to Steiner Tree
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Breaching the 2-Approximation Barrier for Connectivity Augmentation
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Introduction: Survivable Network Design
- 3 Connectivity Augmentation Problem
- 4 State of the art
- 5 Classification of Links
- 6 Cross
- 7 Reduction to Steiner Tree
- 8 Reduction to the Steiner Tree Problem
- 9 Reduction from CAP to Steiner Tree
- 10 Lower Bound
- 11 Obtaining Approximation Algorithm
- 12 Steiner Tree Algorithm
- 13 Our Marking Scheme
- 14 Upper Bound for c
- 15 Analysis of the Approximation Factor
- 16 Grouping
- 17 Open Problems
