The $(2,k)$-connectivity augmentation problem: Algorithmic aspects

Abstract

Durand de Gevigney and Szigeti \cite{DgGSz} have recently given a min-max theorem for the $(2,k)$-connectivity augmentation problem. This article provides an $O(n^3(m+nlogn))$ algorithm to find an optimal solution for this problem.