JMSS Cover
Frequency: Continuous
ISSN: 1549-3644 (Print)
ISSN: 1558-6359 (Online)
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

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.

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

Open AccessCopyright: © 2020 Phanindra Prasad Bhandari, Shree Ram Khadka, Stefan Ruzika and Luca E. Schäfer. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

  • 3,345 Views
  • 1,324 Downloads
  • 2 Citations

Download

Keywords

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