NP-Complete Reductions: Clique, Independent Set, Vertex Cover, and Dominating Set
This lecture covers NP-Complete reductions focusing on Clique, Independent Set, Vertex Cover, and Dominating Set problems. The corrected definition for Vertex Cover is included, along with prerequisites and detailed explanations.
Algorithms with Attitude
46.2K views • Jan 19, 2021
About this video
The previous version had a flawed definition (for Vertex Cover), which has been fixed here.
Table of Contents:
00:00 - Introduction and Prerequisites:
00:28 - Independent Set Definition
01:17 - Reducing Independent Set to/from Clique
02:53 - Vertex Cover Definition
03:39 - Reducing Independent Set to/from Vertex Cover
04:24 - Reduction Compositions
05:00 - NP-Hard and NP-Complete Definitions
06:02 - Proving additional problems NP-Hard
07:09 - Dominating Set Definition
08:13 - Reducing Vertex Cover to Dominating Set
12:38 - Up Next
Table of Contents:
00:00 - Introduction and Prerequisites:
00:28 - Independent Set Definition
01:17 - Reducing Independent Set to/from Clique
02:53 - Vertex Cover Definition
03:39 - Reducing Independent Set to/from Vertex Cover
04:24 - Reduction Compositions
05:00 - NP-Hard and NP-Complete Definitions
06:02 - Proving additional problems NP-Hard
07:09 - Dominating Set Definition
08:13 - Reducing Vertex Cover to Dominating Set
12:38 - Up Next
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
46.2K
Likes
664
Duration
13:23
Published
Jan 19, 2021
User Reviews
4.6
(9) Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.