The Constrained Path Augmentation Problem

In this thesis,we consider the constrained path augmenrtation problem,which is defined as follows:given a weighted directed graph D=(V,A;w;s,.t),where w:A →R+,s,t ∈ V,and a subgraph D0=(V0,A0).It is asked to find an arc set A1(?)A\A0,to satisfy the fact that there is still a directed path from s to t in the reduced subgraph D)[A0∪A1\A2],the objective is to minimize the weight w(A1)=Σe∈A1 w(e),A2 is a set of any k arcs from A0.For this problem,we prove that it is Max-SNP-hard and then design a(k + 1)-approximation algorithm with time complexity O((k + 2)nm);For its special case,where there are k arc-disjoint,directed paths in D0,we design an optimal algorithm with time complexity O((k+1)nm).