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


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.


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.



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