|
|
|
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:
| 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} |