Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

On Element Connectivity Preserving Graph Simplification

Hausdorff Center for Mathematics via YouTube

Overview

Explore a lecture on element-connectivity preserving graph simplification, focusing on a crucial reduction step that maintains element-connectivity in network design and routing problems. Delve into new proofs using setpairs and discover algorithmic advancements for basic element-connectivity problems. Learn about the application of submodularity properties to develop faster algorithms and gain insight into open problems in the field. Examine topics such as packing Steiner trees and forests, internally node-disjoint Steiner trees, and the Cheriyan-Salavatipour Algorithm. Investigate algorithmic aspects, including single pair, all-pair, and global connectivity, as well as approximation techniques in this comprehensive exploration of graph theory and combinatorial optimization.

Syllabus

Intro
Element Connectivity
Motivation/Applications
Rest of the Talk
Packing Steiner trees & forests
Packing internally node- disjoint Steiner trees
Key tool: a graph simplification step
After reduction
Back to packing element- disjoint trees
Cheriyan-Salavatipour Algorithm
Packing bases in polymatroids
Algorithm is same
Packing edge-disjoint Steiner trees
Packing Steiner forests
Packing Elem-Disjoint Steiner forests
Open Problems
Special Case
Switching Topics
Algorithmic Aspects
Single Pair
All-Pair Connectivity
Global Connectivity
A little less naïve algorithm
Finding contractible edge incident to p
Run Times
Approximations

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of On Element Connectivity Preserving Graph Simplification

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.