TR-2007-07

An algorithm to increase the node-connectivity of a digraph by one

András Frank, László Végh

Published in:
Discrete Optimization, 5 (4), pp. 677-684.



Abstract

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


Last modification: 5.6.2018. Please email your comments to Tamás Király!