ABSTRACT
Let G = (V, E) be a weighted digraph with vertex-set V, and edge-set E, and whose edge-set has weight functions T: E —*R* and C: E -+R* (where R* are the non-negative real numbers). Moreover, let s and t be two distinguished vertices of G. A path P=(V, E) is a digraph with vertex-set V=fvj, v2, ..., vk} of distinct vertices, and edge-set E={(vj ,v2), (v2 ,v3),..., (v k.j, v k)}. If s=V], and t=vh then we call this path a {sj}-path. Moreover, given a path P, let z(P) and s(P) represent the sum of the weights of the edges of P with regard to T or C, respectively. Let Pshort (G,T) be the shortest path between s and / in G with respect to the weight function T. Moreover, \QtG' = (V,E') be a spanning subgraph of G and let X be a bound. We formulate the following optimization problem:
0 : Minimize / t C(e)
Such that
r(Pshort (G* T))<k, where
G* = (V,E\JE"). Informally, this problem is to extend a digraph G' with edges from its supergraph G such that the sum of the costs of the new edges is minimum, and in the new graph there exists a path between s and / that meet the A-constraint. For future references we are going to call this problem Minimal Extension Graph Problem or ME problem for short.
