International Journal of Applied Information Systems |
Foundation of Computer Science (FCS), NY, USA |
Volume 5 - Number 3 |
Year of Publication: 2013 |
Authors: Pawan Tamta, Bhagwati Prasad Pande, H. S. Dhami |
10.5120/ijais12-450870 |
Pawan Tamta, Bhagwati Prasad Pande, H. S. Dhami . Reduction of Maximum Flow Network Interdiction Problem: Step towards the Polynomial Time Solutions. International Journal of Applied Information Systems. 5, 3 ( February 2013), 25-29. DOI=10.5120/ijais12-450870
In the present work an attempt is being made to reduce the Maximum Flow Network Interdiction Problem (MFNIP) in to the Subset Sum Problem so as to get some algorithms solvable in polynomial time. Previously developed algorithms are either applicable to some special cases of MFNIP or they do not have a constant performance guarantee. Our reduction has paved the way towards the development of fully polynomial time approximation schemes for Maximum Flow Network Interdiction Problem.