Song song hóa thuật toán Ford Fulkerson tìm luồng cực đại trên mạng đồ thị

Parallelizing Ford Fulkerson algorithm to find maximum flow in a Graph Network
Nơi đăng: proceedings CSE, EUC and DCABES 2016, PARIS 24-26/08/2016, Số: 2016, Trang: 748-752, Năm: 2016, Loại bài viết: Bài báo, Quốc gia: Quốc tế.

Tóm tắt:

Bài toán tìm luồng cực đại trên mạng là bài toán rất thú vị và có nhiều ứng dụng trong thực thế, giao thông. Thuật toán Ford Fullkerson là thuật toán tìm luồng cực đại dùng đường đi tăng luồng. Trong bài báo này, chúng tôi xây dựng thuật toán trên đa bộ xử lý để thực hiện tính toán cho thuật toán FF. Kết quả được hệ thống và chứng minh.

Abstract:

The problem of finding maximum flow in network graph is extremely interesting and practically applicable in many fields in our daily life, especially in transportation. The Ford Fulkerson algorithm is a simple algorithm to solve the maximum flow problem based on the idea of augmenting path from the source vertex. In this paper, we build this algorithm on multiple processors (Master-Slave) to improve computing performance for Ford Fulkerson algorithm. The results of this paper are basically  systematized and proven. The idea of this algorithm is using multi  processors to work in parallel by Ford Fulkerson algorithm