19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Polynomial cases of hypergraph local edge-connectivity augmentation
Presented by Mr. roland GRAPPE
Type: Oral presentation
Track: Algorithmic Graph Theory
Content
Cosh et al. proved that, given a hypergraph H and local edge-connectivy requirements, finding a minimum number of graph edges to be added to H in order to satisfy the requirements is NP-complete. We prove a minimax theorem and a polynomial algorithm solving two subcases of the above problem. Our proof relies on a slight generalization of Mader’s splitting off theorem to hypergraphs.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled