Lexicographically Maximum Flows under an Arc Interdiction

Authors

  • Phanindra Prasad Bhandari Khwopa Engineering Colleg, Bhaktapur, Nepal
  • Shree Ram Khadka Tribhuvan University, Kathmandu, Nepal

DOI:

https://doi.org/10.3126/jnms.v4i2.41459

Keywords:

Network flow, Capacitated vertices, Lexicographically maximum flows, Network interdiction problem

Abstract

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.

Downloads

Download data is not yet available.
Abstract
118
PDF
106

Author Biographies

Phanindra Prasad Bhandari, Khwopa Engineering Colleg, Bhaktapur, Nepal

Science and Humanities Department

Shree Ram Khadka, Tribhuvan University, Kathmandu, Nepal

Central Department of Mathematics

Downloads

Published

2021-12-17

How to Cite

Bhandari, P. P., & Khadka, S. R. (2021). Lexicographically Maximum Flows under an Arc Interdiction. Journal of Nepal Mathematical Society, 4(2), 8–14. https://doi.org/10.3126/jnms.v4i2.41459

Issue

Section

Articles