Lexicographically Maximum Dynamic Flow with Vertex Capacities
- 1 Tribhuvan University, Nepal
- 2 Technische Universitat Kaiserslautern, Germany
Published On: 24 July 2020
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.
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