.png){kind=icon}
.png){kind=icon}
Return
Carousel greedy algorithms for the minimum stretch spanning tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2025.107229.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The minimum stretch spanning tree problem aims to find a spanning tree that minimizes the maximum ratio of the distance in the spanning tree to that in the original graph between each possible pair of vertices. Existing heuristic algorithms for this problem are either computationally expensive or they often produce solutions with significant optimality gaps. In this paper, we introduce a straightforward and promising carousel greedy algorithm to tackle this challenging combinatorial optimization problem. By investigating the properties of the problem, we further enhance the algorithm’s performance. Our algorithm significantly outperforms the best-known algorithms in the literature for both unweighted and weighted graphs, demonstrating superior solution quality with efficient running time.
Keywords:
minimum stretch spanning tree
combinatorial optimization
greedy algorithm
heuristic methods
graph theory
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W