  A dynamic flow network consists of a directed graph, where nodes called
sources represent locations of evacuees, and nodes called sinks represent
locations of evacuation facilities. Each source and each sink are given supply
representing the number of evacuees and demand representing the maximum number
of acceptable evacuees, respectively. Each edge is given capacity and transit
time. Here, the capacity of an edge bounds the rate at which evacuees can enter
the edge per unit time, and the transit time represents the time which evacuees
take to travel across the edge. The evacuation completion time is the minimum
time at which each evacuees can arrive at one of the evacuation facilities.
Given a dynamic flow network without sinks, once sinks are located on some
nodes or edges, the evacuation completion time for this sink location is
determined. We then consider the problem of locating sinks to minimize the
evacuation completion time, called the sink location problem. The problems have
been given polynomial-time algorithms only for limited networks such as paths,
cycles, and trees, but no polynomial-time algorithms are known for more complex
network classes. In this paper, we prove that the 1-sink location problem can
be solved in polynomial-time when an input network is a grid with uniform edge
capacity and transit time.
