Главная
Study mode:
on
1
Intro
2
Element Connectivity
3
Motivation/Applications
4
Rest of the Talk
5
Packing Steiner trees & forests
6
Packing internally node- disjoint Steiner trees
7
Key tool: a graph simplification step
8
After reduction
9
Back to packing element- disjoint trees
10
Cheriyan-Salavatipour Algorithm
11
Packing bases in polymatroids
12
Algorithm is same
13
Packing edge-disjoint Steiner trees
14
Packing Steiner forests
15
Packing Elem-Disjoint Steiner forests
16
Open Problems
17
Special Case
18
Switching Topics
19
Algorithmic Aspects
20
Single Pair
21
All-Pair Connectivity
22
Global Connectivity
23
A little less naïve algorithm
24
Finding contractible edge incident to p
25
Run Times
26
Approximations
Description:
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.

On Element Connectivity Preserving Graph Simplification

Hausdorff Center for Mathematics
Add to list