Data Delivery by Energy-Constrained Mobile Agents on a Line

We consider n mobile agents of limited energy that are placed on a straight line and that need to collectively deliver a single piece of data from a given source point s to a given target point t on the line. Agents can move only as far as their batteries allow. They can hand over the data when they meet. In this paper we show that deciding whether the agents can deliver the data is (weakly) NP-complete, and for instances where all input values are integers, we present a quasi-, pseudo-polynomial time algorithm that runs in time O(Δ2 ·n 1 + 4logΔ), where Δ is the distance between s and t. This answers an open problem stated by Anaya et al.(DISC 2012).