Directed vertex-connectivity augmentation (Q1300059): Difference between revisions

The authors continue the study of the problem of finding a smallest set of new edges to be added to a given digraph to make it \(k\)-vertex-connected. First they prove some theoretical results about this problem, and then they give a combinatorial algorithm which solves this problem optimally in time \(O(k^6)\), for every fixed \(k\geq 1\).