19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Polynomial cases of hypergraph local edge-connectivity augmentation

Presented by Mr. roland GRAPPE
Type: Oral presentation
Track: Algorithmic Graph Theory


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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors