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 ε 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 dT(s,v) ≤ α. dG(s,v) + β (α, β ≥ 0) for every v ε V, here, dT(s,v) is the distance from s to t in T, dG(s,v) is the distance from s to t in G, both α and β are constants. The objective is to minimize the total expanding cost of all the edges in T, that is, min ∑e∊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 α ≡ 1, β ≡ 0 in the constraint condition dT(s,v) ≤ α. dG(s,v) + β (α, β ≥ 0) for every vertex v ε 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 ε V as a root), such that the total expanding cost of all the edges in T is minimum, that is, min ∑e∊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.