Widest Path in Networks with Gains/Losses

In this paper, the generalized widest path problem (or generalized maximum capacity problem) is studied. This problem is denoted by the GWPP. The classical widest path problem is to find a path from a source (s) to a sink (t) with the highest capacity among all possible s-t paths. The GWPP takes int...

Full description

Saved in:
Bibliographic Details
Published in:Axioms 2024-02, Vol.13 (2), p.127
Main Authors: Tayyebi, Javad, Rîtan, Mihai-Lucian, Deaconu, Adrian Marius
Format: Article
Language:English
Subjects:
Algorithms
combinatorial optimization
GPU parallelization
Internet
Mathematical research
maximum capacity path
Metabolism
Metabolites
Methods
Network analysis (Planning)
Networks
Optimization
Path analysis
Polynomials
strongly polynomial algorithms
widest path
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, the generalized widest path problem (or generalized maximum capacity problem) is studied. This problem is denoted by the GWPP. The classical widest path problem is to find a path from a source (s) to a sink (t) with the highest capacity among all possible s-t paths. The GWPP takes into account the presence of loss/gain factors on arcs as well. The GWPP aims to find an s-t path considering the loss/gain factors while satisfying the capacity constraints. For solving the GWPP, three strongly polynomial time algorithms are presented. Two algorithms only work in the case of losses. The first one is less efficient than the second one on a CPU, but it proves to be more efficient on large networks if it parallelized on GPUs. The third algorithm is able to deal with the more general case of losses/gains on arcs. An example is considered to illustrate how each algorithm works. Experiments on large networks are conducted to compare the efficiency of the algorithms proposed.
ISSN:2075-1680
2075-1680
DOI:10.3390/axioms13020127