Abstract (Tibor Jordan)

An important problem in the design of a telephone network is to find a set of new links to be added to an existing network so that the sum of the placement costs is minimized and certain survivability conditions are ensured. For instance one may require that the destruction of any single link must not disconnect any two nodes, etc.

The corresponding problem in graph theory consists of augmenting a graph or digraph by adding a minimum cost set of new edges so that some prescribed connectivity conditions are satisfied.

In this talk we investigate the following version of the problem:

The network is represented by a digraph and the (edge-)connectivity requirements are uniform, say the existence of at least l edge-disjoint paths must be guaranteed in the augmented graph. Furthermore, we need an optimal solution which has the property that at a later phase (when the survivability of the network must be improved again) it can be extended to an optimal k-edge-connected augmentation of the original network for any l<k.

We will show that if the costs are uniform, such an extendable solution always exists and can be found in polynomial time.

This talk is based on joint work with Eddie Cheng (Waterloo).


Last modified: October 26, 1995.
Kim Skak Larsen (kslarsen@imada.sdu.dk)