.png){kind=icon}
.png){kind=icon}
Return
The Rainbow Steiner Tree Problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2021.105621.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Steiner tree
Edge-colored graphs
Spanning tree
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W