文章基本信息

标题：Sequential and Parallel Algorithm to find Maximum Flow on Extended Mixed Networks by Revised Postflow-Pull Methods
本地全文：下载
作者：Lau Nguyen Dinh ; Tran Quoc Chien
期刊名称：Computer Science & Information Technology
电子版ISSN：2231-5403
出版年度：2015
卷号：5
期号：15
页码：29-41
DOI：10.5121/csit.2015.51504
出版社：Academy & Industry Research Collaboration Center (AIRCC)
摘要：The problem of finding maximum flow in network graph is extremely interesting andpractically applicable in many fields in our daily life, especially in transportation. Therefore, alot of researchers have been studying this problem in various methods. Especially in 2013, wehas developed a new algorithm namely, postflow-pull algorithm to find the maximum flow ontraditional networks. In this paper, we revised postflow-push methods to solve thisproblem of finding maximum flow on extended mixed network. In addition, to take moreadvantage of multi-core architecture of the parallel computing system, we build thisparallel algorithm. This is a completely new method not being announced in the world. Theresults of this paper are basically systematized and proven. The idea of this algorithm is usingmulti processors to work in parallel by postflow_push algorithm. Among these processors,there is one main processor managing data, sending data to the sub processors, receiving datafrom the sub-processors. The sub-processors simultaneously execute their work and send theirdata to the main processor until the job is finished, the main processor will show the results ofthe problem.
关键词：Processor; alogrithm; maximum flow; extended mixed network; parallel.