Seminario Dottorato: Edge-connectivity augmentation

Wednesday 9 June 2010 - Roland Grappe

ARGOMENTI: Seminars Ph.D. Program

Wednesday 9 June 2010 h. 14:30, room 1BC/50
Roland Grappe (Univ. Padova - Dip. Mat.)
"Edge-connectivity augmentation"

A graph is k-edge-connected if there exist k edge-disjoint paths between every pair of vertices. The problem of global edge-connectivity augmentation of a graph is as follows: given a graph and an integer k, add a minimum number of edges to the graph in order to make it k-edge-connected.
We will comprehensively focus on this problem and the simple method of Frank that solves it. Then, we will see a few generalizations such as edge-connectivity augmentation of a graph with partition constraints (Bang-Jensen et al.), edge-connectivity augmentation of a hypergraph (Bang-Jensen and Jackson), and the unification of these two results (joint work with Bernath and Szigeti). Eventually, these problems can be formulated in an abstract form, leading to further generalizations.

Rif. int. C. Marastoni, T. Vargiolu, M. Dalla Riva

Download Seminario Dottorato