Fast FPT-Approximation of Branchwidth
Offered By: Hausdorff Center for Mathematics via YouTube
Course Description
Overview
Explore a comprehensive lecture on fast FPT-approximation of branchwidth, delivered by Tuukka Korhonen at the Hausdorff Center for Mathematics. Delve into the concept of branchwidth and its role in decomposing graphs and connectivity functions into tree-like structures. Discover a novel framework for designing fixed-parameter tractable 2-approximation algorithms for branchwidth of connectivity functions. Examine the two key ingredients of this framework: a structural theorem and efficient implementation of refinement operations. Learn about specific applications of this general framework and gain insights into graph parameters, algorithms, and formulas related to branchwidth approximation. The 32-minute talk, which includes an introduction, definitions, and detailed explanations, is based on joint work with Fedor Fomin.
Syllabus
Intro
Definition of Branchwidth
Framework
Graph Parameters
Algorithm
Formula
Explanation
Refinement
Taught by
Hausdorff Center for Mathematics
Related Courses
Natural Language ProcessingColumbia University via Coursera Intro to Algorithms
Udacity Conception et mise en œuvre d'algorithmes.
École Polytechnique via Coursera Paradigms of Computer Programming
Université catholique de Louvain via edX Data Structures and Algorithm Design Part I | 数据结构与算法设计(上)
Tsinghua University via edX