Published in:
Discrete Optimization, 5 (4), pp. 677-684.
We develop a combinatorial polynomial-time algorithm to make a (k-1)-connected digraph k-connected by adding a minimum number of new edges. In \cite{FJ95} a min-max theorem was proved (in a more general form) for the minimum number of new edges whose addition makes a (k-1)-connected directed graph k-connected. In this paper we describe a new, constructive proof that gives rise to a combinatorial polynomial-time algorithm.
Bibtex entry:
@techreport{egres-07-07,
AUTHOR | = | {Frank, Andr{\'a}s and V{\'e}gh, L{\'a}szl{\'o}}, |
TITLE | = | {An algorithm to increase the node-connectivity of a digraph by one}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2007}, |
NUMBER | = | {TR-2007-07} |