Research Article Open Access

Lexicographically Maximum Dynamic Flow with Vertex Capacities

Phanindra Prasad Bhandari1, Shree Ram Khadka1, Stefan Ruzika2 and Luca E. Schäfer2
  • 1 Tribhuvan University, Nepal
  • 2 Technische Universitat Kaiserslautern, Germany
Journal of Mathematics and Statistics
Volume 16 No. 1, 2020, 142-147

DOI: https://doi.org/10.3844/jmssp.2020.142.147

Submitted On: 11 June 2020
Published On: 24 July 2020

How to Cite: Bhandari, P. P., Khadka, S. R., Ruzika, S. & Schäfer, L. E. (2020). Lexicographically Maximum Dynamic Flow with Vertex Capacities. Journal of Mathematics and Statistics, 16(1), 142-147. https://doi.org/10.3844/jmssp.2020.142.147

Abstract

We consider an evacuation planning problem in the sense of computing a feasible dynamic flow lexicographically maximizing the amount of flow entering a set of terminals with respect to a given prioritization and given vertex capacities. We propose a polynomial time algorithm for the static version of the problem and a pseudo-polynomial time algorithm for the dynamic case. We show that by neglecting the vertex capacities, the dynamic version can be solved in polynomial time by using temporally repeated flows.

Download

Keywords

  • Evacuation Planning
  • Disaster Management
  • Lexicographically Maximum Flows
  • Dynamic Flows
  • Vertex Capacities