Open AccessLexicographically Maximum Flows under an Arc Interdiction
Author(s) -
Phanindra Prasad Bhandari,
Sundar Khadka
Publication year - 2021
Publication title -
journal of nepal mathematical society
Language(s) - English
Resource type - Journals
eISSN - 2616-0161
pISSN - 2616-0153
DOI - 10.3126/jnms.v4i2.41459
Subject(s) - interdiction , lexicographical order , flow network , residual , transshipment (information security) , arc (geometry) , maximum flow problem , flow (mathematics) , computer science , mathematical optimization , mathematics , operations research , algorithm , combinatorics , engineering , geometry , aerospace engineering
Network interdiction problem arises when an unwanted agent attacks the network system to deteriorate its transshipment efficiency. Literature is flourished with models and solution approaches for the problem. This paper considers a single commodity lexicographic maximum flow problem on a directed network with capacitated vertices to study two network flow problems under an arc interdiction. In the first, the objective is to find an arc on input network to be destroyed so that the residual lexicographically maximum flow is lexicographically minimum. The second problem aims to find a flow pattern resulting lexicographically maximum flow on the input network so that the total residual flow, if an arc is destroyed, is maximum. The paper proposes strongly polynomial time solution procedures for these problems.