Successive edge-connectivity augmentation problems

It was known (see [8]) that for undirected edge-connectivity land for unifo rm demands) the Successive Augmentation Property holds, i.e. for any starti ng graph G with edge-connectivity l there exists a sequence G = G(0), G(1), G(2),... of supergraphs of G such that G(i) is a subgraph of G(j) for any i < j and G(i) is an optimal (l + i)-edge-connected augmentation of G for a ny i greater than or equal to 0. In this paper we will show that the augmentation algorithm of A. Frank [3] can also be used to solve the corresponding Successive Edge-Augmentation Pr oblem and implies (a stronger version of) the Successive Augmentation Prope rty, even for some non-uniform demands. In addition we show the - previously unknown - Successive Augmentation Prop erty for directed edge connectivity (in the case of uniform demands). For several possible extensions and for the two vertex-connectivity version s counter-examples are given.