@inproceedings{b48a5c003eb44e79aaa2bb66acdcdb07,
title = "Graph Exploration by Energy-Sharing Mobile Agents",
abstract = "We consider the problem of collective exploration of a known n-node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an n-node path, we give an O(n+ k) time algorithm that either finds an exploration strategy, or reports that one does not exist. For an n-node tree with ℓ leaves, we give an O(n+ ℓk2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal.",
keywords = "Energy, Exploration, Graph, Mobile agent, Path, Sharing, Tree",
author = "Jurek Czyzowicz and Stefan Dobrev and Ryan Killick and Evangelos Kranakis and Danny Krizanc and Lata Narayanan and Jaroslav Opatrny and Denis Pankratov and Sunil Shende",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021 ; Conference date: 28-06-2021 Through 01-07-2021",
year = "2021",
doi = "10.1007/978-3-030-79527-6_11",
language = "English (US)",
isbn = "9783030795269",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "185--203",
editor = "Tomasz Jurdzi{\'n}ski and Stefan Schmid",
booktitle = "Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings",
address = "Germany",
}