text: abstract
  we present a novel approach to finding the k-sink on dynamic path networks with general edge
  capacities. our first algorithm runs in o(n log n + k 2 log4 n) time, where n is the number of
  vertices on the given path, and our second algorithm runs in o(n log3 n) time. together, they
  improve upon the previously most efficient o(kn log2 n) time algorithm due to arumugam et
  al. [1] for all values of k. in the case where all the edges have the same capacity, we again present
  two algorithms that run in o(n + k 2 log2 n) time and o(n log n) time, respectively, and they
  together improve upon the previously best o(kn) time algorithm due to higashikawa et al. [10]
  for all values of k.
  1998 acm subject classification f.2.2
  keywords and phrases facility location, k-sink, parametric search, dynamic path network
  digital object identifier 10.4230/lipics...