.png){kind=icon}
返回
The Rainbow Steiner Tree Problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2021.105621.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Given an undirected and edge-colored graph with non-negative edge lengths, the aim of the Rainbow Steiner Tree Problem (RSTP) is to find a minimum Steiner Tree that uses at most one edge for each color. In this paper, the RSTP is introduced, a mathematical model is proposed to formally represent the problem and its theoretical properties are investigated. Since the RSTP belongs to the NP-class, two heuristic methods are designed: a Lagrangian relaxation approach and a multistart algorithm. Extensive computational experiments are carried out on a significant set of test problems to empirically evaluate the performance of the proposed approaches. The computational results show that the two approaches are both effective and efficient compared to the ILOG CPLEX solver.
Keyword:
Steiner tree
Edge-colored graphs
Spanning tree
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
An NMR crystallography DFT-D approach to analyse the role of intermolecular hydrogen bonding and π–π interactions in driving cocrystallisation of indomethacin and nicotinamide.png)
CrystEngComm
CrystEngCommIF0
PREAI
分享收藏
Breakout local search for the Steiner tree problem with revenue, budget and hop constraints具有收入，预算和跳限制的Steiner树问题的突围局部搜索
PREAI
分享收藏
查看更多内容