CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Development of an Algorithm for all type of Network Flow Problems

by Pawan Tamta, B. P. Pande, H. S. Dhami
journal cover thumbnail

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

@article{ 10.5120/5784-8109,
author = { Pawan Tamta, B. P. Pande, H. S. Dhami },
title = { Development of an Algorithm for all type of Network Flow Problems },
journal = { International Journal of Computer Applications },
issue_date = { March 2012 },
volume = { 42 },
number = { 17 },
month = { March },
year = { 2012 },
issn = { 0975-8887 },
pages = { 16-19 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume42/number17/5784-8109/ },
doi = { 10.5120/5784-8109 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:31:32.892923+05:30
%A Pawan Tamta
%A B. P. Pande
%A H. S. Dhami
%T Development of an Algorithm for all type of Network Flow Problems
%J International Journal of Computer Applications
%@ 0975-8887
%V 42
%N 17
%P 16-19
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, Upper Saddle River (1993).
  2. N. Assimakopoulos, A network interdiction model for hospital infection control, Computers in Biology and Medicine 17 (1987), pp. 413–422
  3. L. Bingol, A Lagrangian heuristic for solving a network interdiction problem, Master's thesis, Naval Postgraduate School, 2001.
  4. G. G. Brown, M. W. Carlyle, J. Salmerón and R. K. Wood, Defending critical infrastructure, Interfaces 36 (2006), pp. 530–544
  5. 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.
  6. 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. |
  7. K. J. Cormican, D. P. Morton and R. K. Wood, Stochastic network interdiction, Operations Research 46 (1998), pp. 184–197.
  8. D. Du and R. Chandrasekaran, The maximum residual flow problem: NP-hardness with two-arc destruction, Networks 50 (2007), pp. 181–182.
  9. 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.
  10. E. Israeli and R. K. Wood, Shortest-path network interdiction, Networks 40 (2002), pp. 97–111
  11. U. Janjarassuk and J. T. Linderoth, Reformulation and sampling to solve a stochastic network interdiction problem, Networks 52 (2008), pp. 120–132.
  12. C. Lim and J. C. Smith, Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Transactions 39 (2007), pp. 15–26.
  13. A. W. McMasters and T. M. Mustin, Optimal interdiction of a supply network, Naval Research Logistics Quarterly 17 (1970), pp. 261–268.
  14. C. A. Phillips, The network inhibition problem, in: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993 pp. 776–785.
  15. 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.
  16. 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.
  17. A. Schrijver, On the history of the transportation and the maximum flow problems, Mathematical Programming 91 (2002), pp. 437–445
  18. A. Uygun, Network interdiction by Lagrangian relaxation and branch-and- bound, Master's thesis, Naval Postgraduate School, 2002.
  19. R. K. Wood, Deterministic network interdiction, Mathematical and Computer Modelling 17 (1993), pp. 1–18.
Index Terms

Computer Science
Information Sciences

Keywords

Maximum Flow Network Problem (mfnp) Simple Path Disjoint Network Polynomial Time Algorithm

Powered by PhDFocusTM