.png){kind=icon}
返回
Determining the Minimum Cost Steiner Tree for Delay Constrained Problems
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2021.3122024.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We address a variant of the Steiner tree problem for delay constrained problems. The addressed problem consists in determining the minimum cost Steiner tree, while guaranteeing that the delay between any two terminal nodes does not exceed a given maximum value. This problem is known as the bounded diameter Steiner minimum tree problem. We propose a compact formulation based on integer linear programming (ILP) to obtain optimal solutions, which was efficiently solved on two telecommunication core networks up to 75 nodes. However, given that for traditional Steiner tree graphs the ILP proved to be inefficient, we propose a heuristic method and compare it with the ILP formulation. We show that the heuristic provides optimal solutions, except for two cases in our experiments where it provided near-optimal solutions, always in reasonable runtimes. Additionally, to reduce the complexity of the problem, we propose some novel and modified graph reductions specific for the addressed problem.
Keyword:
Delays
Steiner trees
Costs
Routing
Integer linear programming
Heuristic algorithms
Control systems
Delay-constrained
graph reductions
heuristic
integer linear programming
Steiner tree problem
期刊
IF:
3.6
论文数:
9.8W
被引数:
29.4W
机构
引用论文
.png){kind=icon}
Reactivity Studies of a Stable N-Heterocyclic Silylene with Triphenylsilanol and Pentafluorophenol
PREAI
分享收藏
查看更多内容