On Element Connectivity Preserving Graph Simplification
Hausdorff Center for Mathematics via YouTube
Overview
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