YoVDO

Approximation Algorithms for Hitting Subgraphs

Offered By: Fields Institute via YouTube

Tags

Approximation Algorithms Courses Combinatorial Algorithms Courses Coloring Courses

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

Comparing Genes, Proteins, and Genomes (Bioinformatics III)
University of California, San Diego via Coursera Molecular Evolution (Bioinformatics IV)
University of California, San Diego via Coursera Reconfiguring Simple ST Hamiltonian Paths in Rectangular Grid Graphs
Fields Institute via YouTube How to Allow Deep Learning on Your Data Without Revealing Your Data
Institute for Pure & Applied Mathematics (IPAM) via YouTube Face Structures of Tropical Polyhedra
Hausdorff Center for Mathematics via YouTube