Research Article
Max-flow Min-cut Algorithm in Spark with Application to Road Networks
@INPROCEEDINGS{10.1007/978-3-319-58967-1_2, author={Varun Ramesh and Shivanee Nagarajan and Saswati Mukherjee}, title={Max-flow Min-cut Algorithm in Spark with Application to Road Networks}, proceedings={Big Data Technologies and Applications. 7th International Conference, BDTA 2016, Seoul, South Korea, November 17--18, 2016, Proceedings}, proceedings_a={BDTA}, year={2017}, month={6}, keywords={}, doi={10.1007/978-3-319-58967-1_2} }- Varun Ramesh
Shivanee Nagarajan
Saswati Mukherjee
Year: 2017
Max-flow Min-cut Algorithm in Spark with Application to Road Networks
BDTA
Springer
DOI: 10.1007/978-3-319-58967-1_2
Abstract
The max-flow min-cut problem is one of the most explored and studied problems in the area of combinatorial algorithms and optimization. In this paper, we solve the max-flow min-cut problem on large random graphs with log-normal distribution of outdegrees using the distributed Edmonds-Karp algorithm. The algorithm is implemented on a cluster using Spark. We compare the runtime between a single machine implementation and cluster implementation and analyze the impact of communication cost on runtime. In our experiments, we observe that the practical value recorded across various graphs is much lesser than the theoretical estimations primarily due to smaller diameter of the graph. Additionally, we extend this model theoretically on a large urban road network to evaluate the minimum number of sensors required for surveillance of the entire network. To validate the feasibility of this theoretical extension, we tested the model with a large log-normal graph with 1.1 million edges and obtained a max-flow value of 54, which implies that the minimum-cut set of the graph consists of 54 edges. This is a reasonable set of edges to place the sensors compared to the total number of edges. We believe that our approach can enhance the safety of road networks throughout the world.