Approximation Algorithms for Hitting Subgraphs
Offered By: Fields Institute via YouTube
Course Description
Overview
Explore approximation algorithms for hitting subgraphs in this 29-minute conference talk from the 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021). Presented by Noah Brüstle from McGill University, delve into topics such as inapproximability, NP-Hardness, good subgraphs, and semi-symmetric cut vertices. Learn about the coloring technique and gain insights into this complex area of graph theory. Conclude with a summary of key findings and potential future research directions in the field of combinatorial algorithms.
Syllabus
Intro
Hitting Subgraphs
Approximation Algorithms
Inapproximability
NP-Hardness
Good Subgraphs
Semi-symmetric cut vertices
The coloring
Concluding Remarks
Taught by
Fields Institute
Related Courses
Approximation Algorithms Part IÉcole normale supérieure via Coursera Approximation Algorithms Part II
École normale supérieure via Coursera Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Stanford University via Coursera Algorithm Design and Analysis
University of Pennsylvania via edX Delivery Problem
University of California, San Diego via Coursera