Two Algorithms for the k-Widest Path Problem

Teresa Gomes

doi:10.1007/s10922-023-09738-z

Two Algorithms for the k-Widest Path Problem

2023-06-26

0

PRE

AI

DOI：10.1007/s10922-023-09738-z

原文链接

原文求助

摘要

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

Two Algorithms for the k-Widest Path Problem

摘要

期刊

机构