Lexicographically Maximum Dynamic Flow with Vertex Capacities
- 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.
DOI: https://doi.org/10.3844/jmssp.2020.142.147
Copyright: © 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,429 Views
- 1,392 Downloads
- 2 Citations
Download
Keywords
- Evacuation Planning
- Disaster Management
- Lexicographically Maximum Flows
- Dynamic Flows
- Vertex Capacities