# zbMATH — the first resource for mathematics

Directed vertex-connectivity augmentation. (English) Zbl 0934.05081
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$$.

##### MSC:
 05C40 Connectivity 05C20 Directed graphs (digraphs), tournaments 05C85 Graph algorithms (graph-theoretic aspects) 90C27 Combinatorial optimization
##### Keywords:
vertex-connectivity; digraph; combinatorial algorithm
Full Text: