The restricted minimum single source shortest path tree expansion problem
Haiyan Wang, Wei-Qi Deng, Binchao Huang, Jianping Li · 2017
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)T(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, mine∈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, mine∈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.