×

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
PDF BibTeX XML Cite
Full Text: DOI