On Balanced Edge Connectivity and Applications (abstract)

Let wi: VxV -> Q, i=1,2 be two weight functions on the possible edges of a directed or undirected graph with vertex set V such that for the cut function, the inequality

          
  dw2 := sum      w2(ij) >= 0
         i in T
         j notin T

holds for every T in 2^V. We consider the computation of the value l~(w1,w2,k) defined by

    l~(w1,w2,k) := min(l | dw1(T) + ldw2(T) >= k) for all 0 c T c V

We show that the associated decision problem is NP-complete, but for a class of instances we can give a polynomial time algorithm. This class is closely related to the following bottleneck augmentation problem. Consider a network N=(V,E,c) with a rational valued capacity function c: VxV -> Q+, and let k be a positive, rational number. Consider the problem of finding a capacity function c: VxV -> Q+ such that, in the resulting network N'=(V',E',c+c') the edge connectivity number l{c+c'} is at least k, and the maximal increase c'(ij) is minimal. We give an algorithm which computes such an augmentation in strongly polynomial time.

M.Bussieck@tu-bs.de

May 22 1995