Directed vertex-connectivity augmentation
The problem of finding a smallest set of new edges to be added to a given directed graph to make it k-vertex-connected was shown to be polynomially solvable recently in [6] for any target connectivity k greater than or equal to 1. However, the algorithm given there relied on the ellipsoid method. Here we refine some results of [6] which makes it possible to construct a combinatorial algorithm which is polynomial for any Bred k. Short proofs for (extensions of) some earlier results related to this problem will also be given.
augmentation connectivity of directed graphs polynomial algorithm