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

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

Primary authors

More