The Restricted Minimum Single Source Shortest Path Tree Expansion Problem

We consider three kinds of minimum single source shortest path tree expansion problems. Given an undirected connected graph G = (V, E; w, c, b; s) with n vertexes, m edges and a positive constant H, w(e) is the length of edge e, c(e) is the capacity of edge e, b(e) is the unit cost to increase the capacity of edge e, H is a given capacity restriction value and s is a fixed vertex of G. For every edge e = uv is an element of E, if capacity c(uv) < H, we should increase the capacity of edge uv, and the increasing value is add(uv) = H - c(uv); if capacity c(uv) >= H, we needn't increase the capacity of edge uv, and the increasing value is add(uv) = 0. Find a spanning tree T of G, such that d(T) (s, v) <= alpha . d(G) (s, v) + beta (alpha, beta >= 0) for every v is an element of V, here, d(T) (s, v) is the distance from s to t in T, d(G) (s, v) is the distance from s to t in G, both a and beta are constants. The objective is to minimize the total expanding cost of all the edges in T, that is, min Sigma(e is an element of E(T))add(e) . b(e). We call it the restricted minimum single source shortest path tree expansion problem. The problem is NP-hard, and we design a heuristic algorithm for it. Suppose alpha = 1, beta = 0 in the constraint condition d(T) (s, v) <= alpha . d(G) (s, v) + beta (alpha, beta >= 0) for every vertex v is an element of V, we call the new problem the extended restricted minimum single source shortest path tree expansion problem and design a strongly polynomial-time algorithm for it. On the basis of the extended restricted minimum single source shortest path tree expansion problem, we study a more widespread problem with a different objective: find a single source shortest path tree T (we can use any v is an element of V as a root), such that the total expanding cost of all the edges in T is minimum, that is, min Sigma(e is an element of E(T))add(e) . b(e). We call it the general restricted minimum single source shortest path tree expansion problem, then design a polynomial-time algorithm for it.