Improved algorithms for computing k-sink on dynamic flow path networks

We address the problem of locating k sinks on dynamic flow path networks with n vertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run in O(n log n + k² log⁴ n) and O(n log³ n) time, respectively. When all edges have the same capacity, we also present two algorithms which run in O(n + k² log² n) time and O(n log n) time, respectively. These algorithms together improve upon the previously most efficient algorithms, which have time complexities O(kn log² n) [1] and O(kn) [11], in the general and uniform edge capacity cases, respectively. The above results are achieved by organizing relevant data for subpaths in a strategic way during preprocessing, and the final results are obtained by extracting/ merging them in an efficient manner.