The week's pick
Random Articles
Reseach Article
Development of an Algorithm for all type of Network Flow Problems
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 42 - Number 17 |
| Year of Publication: 2012 |
| Authors: Pawan Tamta, B. P. Pande, H. S. Dhami |
10.5120/5784-8109
|
Pawan Tamta, B. P. Pande, H. S. Dhami . Development of an Algorithm for all type of Network Flow Problems. International Journal of Computer Applications. 42, 17 ( March 2012), 16-19. DOI=10.5120/5784-8109
Abstract
We develop an algorithm which reduces the arbitrary instance of the network flow problem to a simple path disjoint network in polynomial time. Then the flow in each path is taken as the minimum of the arc capacities of that path from where the flow in each arc can be easily determined. The polynomial time algorithm can determine any instance of the network flow problem faster than the previously existing algorithms . An example has been given to elucidate the process. At the end a MATLAB program based on this algorithm has been given.
References
- R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, Upper Saddle River (1993).
- N. Assimakopoulos, A network interdiction model for hospital infection control, Computers in Biology and Medicine 17 (1987), pp. 413–422
- L. Bingol, A Lagrangian heuristic for solving a network interdiction problem, Master's thesis, Naval Postgraduate School, 2001.
- G. G. Brown, M. W. Carlyle, J. Salmerón and R. K. Wood, Defending critical infrastructure, Interfaces 36 (2006), pp. 530–544
- C. Burch, R. D. Carr, M. Marathe, C. A. Phillips and E. Sundberg, A decomposition-based pseudoapproximation algorithm for network flow inhibition. In: D. L. Woodruff, Editor, Network Interdiction and Stochastic Integer Programming, Kluwer Academic Press (2002), pp. 51–68.
- R. L. Church, M. P. Scaparra and R. S. Middleton, Identifying critical infrastructure: The median and covering facility interdiction problems, Annals of the Association of American Geographers 94 (2004), pp. 491–502. |
- K. J. Cormican, D. P. Morton and R. K. Wood, Stochastic network interdiction, Operations Research 46 (1998), pp. 184–197.
- D. Du and R. Chandrasekaran, The maximum residual flow problem: NP-hardness with two-arc destruction, Networks 50 (2007), pp. 181–182.
- T. E. Harris, F. S. Ross, Fundamentals of a method for evaluating rail network capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica, CA.
- E. Israeli and R. K. Wood, Shortest-path network interdiction, Networks 40 (2002), pp. 97–111
- U. Janjarassuk and J. T. Linderoth, Reformulation and sampling to solve a stochastic network interdiction problem, Networks 52 (2008), pp. 120–132.
- C. Lim and J. C. Smith, Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Transactions 39 (2007), pp. 15–26.
- A. W. McMasters and T. M. Mustin, Optimal interdiction of a supply network, Naval Research Logistics Quarterly 17 (1970), pp. 261–268.
- C. A. Phillips, The network inhibition problem, in: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993 pp. 776–785.
- H. D. Ratliff, G. T. Sicilia and S. H. Lubore, Finding the n most vital links in flow networks, Management Science 21 (1975), pp. 531–539.
- J. O. Royset and R. K. Wood, Solving the bi-objective maximum-flow network-interdiction problem, INFORMS Journal on Computing 19 (2007), pp. 175–184.
- A. Schrijver, On the history of the transportation and the maximum flow problems, Mathematical Programming 91 (2002), pp. 437–445
- A. Uygun, Network interdiction by Lagrangian relaxation and branch-and- bound, Master's thesis, Naval Postgraduate School, 2002.
- R. K. Wood, Deterministic network interdiction, Mathematical and Computer Modelling 17 (1993), pp. 1–18.
Index Terms
Keywords