YoVDO

Cut-Equivalent Trees are Optimal for Min-Cut Queries

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Data Structures Courses Approximation Algorithms Courses

Course Description

Overview

Explore a 24-minute IEEE conference talk on cut-equivalent trees and their optimality for min-cut queries. Delve into previous algorithms for constructing Gomory-Hu trees, min-cut data structures, and the equivalence between min-cut data structures and cut-equivalent trees. Learn about the Gomory-Hu algorithm description, tournament expansion, and the challenges of designing fast approximation algorithms. Gain insights from speakers Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi as they discuss their findings and present approximation ideas for this complex graph theory topic.

Syllabus

Introduction
Previous Algorithms for constructing GH Trees
Min-Cut Data-Structure
Equivalence Between Min-Cut Data Structure and Cut-Equivalent Tree
First Result:Yes!
Corollaries
Gomory-Hu Algorithm Description
Tournament
Expansion
Gomory-Hu Fails Using Approx.
Issues with Designing Fast Approx. Algorithms
Approximation Idea


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

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