Name
Abstract | ||
|---|---|---|
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 d
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sub>
(s, v) ≤ α · d
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</sub>
(s, v) + β (α, β ≥ 0) for every v ∈ V, here, d
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sub>
(s, v) is the distance from s to t in T, d
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</sub>
(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
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e∈E(T)</sub>
Σ 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 d
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sub>
(s, v) ≤ α · d
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</sub>
(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
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e∈E(T)</sub>
Σ 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/ICIS.2017.7959970 | 2017 IEEE/ACIS 16th International Conference on Computer and Information Science (ICIS) |
Keywords | Field | DocType |
single source shortest path tree,arborescence,expansion | Combinatorics,Mathematical optimization,Algorithm design,Shortest path problem,Vertex (geometry),Heuristic (computer science),Shortest-path tree,Connectivity,Mathematics,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-1-5090-5508-1 | 0 | 0.34 |
References | Authors | |
4 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haiyan Wang | 1 | 39 | 16.48 |
| Weiqi Deng | 2 | 0 | 0.34 |
| Binchao Huang | 3 | 0 | 0.34 |
| Jianping Li | 4 | 455 | 76.28 |