arrow
返回

Two Algorithms for the k-Widest Path Problem

delete2023-06-26
delete0
PRE
AI
T
Teresa Gomes
L
Lúcia Martins
J
José Craveirinha
D
Deep Medhi *
DOI:10.1007/s10922-023-09738-zdelete
delete原文链接
delete分享
delete收藏
摘要

摘要

En 中文
In communication networks where services require a certain amount of bandwidth for setting up a connection, an important problem (to be referred to as the k-widest path problem) is to enumerate paths in non-increasing order of the bandwidth availability of the paths. For this problem, a path follows a non-additive, concave cost property. Notably, this problem parallels the k-shortest path problem for which the path cost is additive. We present two exact algorithms for solving this problem, denoted by kWP-1 and kWP-2, inspired by the loopless version of MPS (Martins-Pascoal-Santos) algorithm and Yen's algorithm for the k-shortest path algorithm, respectively. Our numerical study shows that kWP-2 is more effective than kWP-1 for the k-widest path problem, in contrast with the relatively better performance of MPS over Yen's algorithm regarding the enumeration of k-shortest paths.
Keyword:
Widest paths
Concave metric
Reduced bandwidth
Deviation algorithms
Path enumeration
Ranking paths
Communication network routing

期刊

Journal of Network and Systems Management 封面图
Journal of Network and Systems Management
IF:
3.9
论文数:
1.1K
被引数:
1.7K

机构

I
inesc coimbra
学者数:
1
论文数: 2
被引数: 120
U
universidade de coimbra
学者数:
300
论文数: 107
被引数: 8.6K
引用论文

引用论文

err分享
err收藏
err分享
err收藏
学者 查看更多内容