.png){kind=icon}
.png){kind=icon}
Return
A fast parallel max-flow algorithm
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2022.07.003.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A new parallel algorithm for the max-flow problem on directed networks with single-source and single -sink is proposed. The algorithm is based on tree sub-networks and on efficient parallel algorithm to compute max-flows on the tree sub-networks. The latter algorithm is proved to be work-optimal and time-optimal. The parallel implementation of the complete algorithm is more efficient than the best known parallel algorithm for the max-flow problem in terms of time-complexity and the sequential implementation of the algorithm achieves the best known sequential time-complexity, without using any complex data-structures or complex manipulations on the network. (C) 2022 Elsevier Inc. All rights reserved.
Keywords:
Combinatorial optimization
Complexity theory
Discrete optimization
Network flow problems
Parallel algorithms
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K