It was known that for undirected edge-connectivity (and for uniform demands) the Successive Augmentation Property holds, i.e. for any starting graph G with edge-connectivity l there exists a sequence G = G0, G1, G2, ... of supergraphs of G such that Gi is a subgraph of Gj for any i < j and Gi is an optimal (l + i)-edge-connected augmentation of G for any i ≥ 0. In this paper we will show that the augmentation algorithm of A. Frank can also be used to solve the corresponding Successive Edge-Augmentation Problem and implies (a stonger version of) the Successive Augmentation Property, even for some non-uniform demands. In addition we show the – previously unknown – Successive Augmentation Property for directed edge-connectivity (in the case of uniform demands). For several possible extensions and for the two vertex-connectivity versions counter-examples are given.
