  We study a problem where k autonomous mobile agents are initially located on
distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous
mobile agent has a predefined velocity and is only allowed to move along the
edges of the graph. We are interested in delivering a package, initially
positioned in a source node s, to a destination node y. The delivery is
achieved by the collective effort of the autonomous mobile agents, which can
carry and exchange the package among them. The objective is to compute a
delivery schedule that minimizes the delivery time of the package. In this
paper, we propose an O(kn log n + km) time algorithm for this problem. This
improves the previous state-of-the-art O(k^2 m + k n^2 + APSP) time algorithm
for this problem, where APSP stands for the running-time of an algorithm for
the All-Pairs Shortest Paths problem.
