Name
Abstract | ||
|---|---|---|
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(kn) + k m) 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-25027-0_12 | FCT |
Field | DocType | Volume |
Graph,Discrete mathematics,Mobile agent,Algorithm,Mathematics | Journal | abs/1904.09142 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Iago A. Carvalho | 1 | 0 | 0.34 |
| Thomas Erlebach | 2 | 7 | 2.40 |
| Kleitos Papadopoulos | 3 | 0 | 0.34 |