event
ARC Colloquium: Laszlo Vegh , Eovtos Lorand University
Primary tabs
Abstract:
In the node-connectivity augmentation problem, we want to add a minimum number of new edges to an undirected graph to make it k-node-connected. The complexity of this question is still open, although the analogous questions of both directed and undirected edge-connectivity and directed node-connectivity augmentation are known to be polynomially solvable.
In my talk, I present a min-max formula and a polynomial time algorithm for the special case when the input graph is already (k-1)-connected. The formula has been conjectured by Frank and Jordan in 1994. I also give an overview of the other three augmentation problems.
Groups
Status
- Workflow Status:Published
- Created By:Elizabeth Ndongi
- Created:11/16/2011
- Modified By:Fletcher Moore
- Modified:10/07/2016
Categories
Keywords
- No keywords were submitted.