Premium
Max‐flow min‐cut algorithm with application to road networks
Author(s) -
Ramesh Varun,
Nagarajan Shivanee,
Jung Jason J.,
Mukherjee Saswati
Publication year - 2017
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4099
Subject(s) - computer science , flow network , spark (programming language) , maximum flow problem , algorithm , extension (predicate logic) , log normal distribution , set (abstract data type) , flow (mathematics) , cluster (spacecraft) , mathematics , mathematical optimization , computer network , statistics , geometry , programming language
Summary 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 lognormal graphs and real‐world datasets using the distributed Edmonds‐Karp algorithm. The algorithm is deployed on a stand‐alone cluster using Spark. In our experiments, we compare the runtime between a single‐machine implementation and cluster implementation. We analyze the impact of communication cost on runtime for large lognormal graphs. Further, we record the runtime of the algorithm for various real‐world datasets having similar average outdegree and number of edges but different diameters. The observations indicate that for such a set of similar graphs, runtime increases slowly with an increase in diameter. Additionally, we apply this model on large urban road networks to evaluate the minimum number of sensors required for surveillance of the entire network. To validate the feasibility of this extension, we tested the model with large road network datasets having more than 2.7 million edges. Thus, we believe that our model can enhance the safety of today's dynamic large urban road networks.