YoVDO

Fast FPT-Approximation of Branchwidth

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Graph Theory Courses Algorithm Design Courses Computational Complexity Courses

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

Aplicaciones de la teoría de grafos a la vida real
Miríadax
Aplicaciones de la Teoría de Grafos a la vida real
Universitat Politècnica de València via UPV [X]
Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX
Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera
Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer