.png){kind=icon}
.png){kind=icon}
Return
Two Algorithms for the k-Widest Path Problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10922-023-09738-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Widest paths
Concave metric
Reduced bandwidth
Deviation algorithms
Path enumeration
Ranking paths
Communication network routing
Journal
IF:
3.9
Papers:
1.0K
Citations:
1.3K