A parallel approach for obtaining maximum flow in a network

Autor:	S Shine, Divya Lissia Joseph
Rok vydání:	2015
Předmět:	Push–relabel maximum flow algorithm Mathematical optimization Computer science Node (networking) Maximum flow problem Closure problem Minimum-cost flow problem Flow network Time complexity Algorithm Multi-commodity flow problem
Zdroj:	2015 International Conference on Control Communication & Computing India (ICCC).
DOI:	10.1109/iccc.2015.7432988
Popis:	Computing flow in a directed graph is a fundamental problem to which other programs can be reduced. The objective associated with the flow networks problem is to maximize the flow through the network. So it is usually studied within the field of Optimization. A parallel approach for obtaining maximum flow in a network is presented here. The concept of layered network is used here. The algorithm proceeds in two passes, forward and backward passes. Each node in a layer are processed in parallel. The time complexity of the algorithm is analyzed to be O(n2logkn).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6b55165b1cd645ef5c126e1a3654dd98 https://doi.org/10.1109/iccc.2015.7432988 Zobrazit plný text záznamu