.png){kind=icon}
返回
New Dynamic Programming algorithm for the Multiobjective Minimum Spanning Tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2024.106852.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The Multiobjective Minimum Spanning Tree (MO-MST) problem generalizes the Minimum Spanning Tree problem by weighting the edges of the input graph using vectors instead of scalars. In this paper, we design a new Dynamic Programming MO-MST algorithm. Dynamic Programming for a MO-MST instance requests solving a One-to-One Multiobjective Shortest Path (MOSP) instance and both instances have equivalent solution sets. The MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost-dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, , we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.
Keyword:
Multiple objective programming
Multiobjective Minimum Spanning Trees
Dynamic Programming
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
Type of Floral Product Purchased and Demographic Characteristics and Floral Knowledge of Consumers.png)
HortScience
OAAI
HortScienceIF0
OAAI分享收藏Multiobjective shortest path problems with lexicographic goal-based preferences具有基于词典目标的偏好的多目标最短路径问题
PREAI
分享收藏
Computing all efficient solutions of the biobjective minimum spanning tree problem计算双目标最小生成树问题的所有有效解
PREAI
分享收藏
查看更多内容