Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Data Delivery by Energy-Constrained Mobile Agents on a Line
verfasst von : Jérémie Chalopin, Riko Jacob, Matúš Mihalák, Peter Widmayer
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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).