Graph Exploration by Energy-Sharing Mobile Agents

Jurek Czyzowicz, Stefan Dobrev, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Sunil Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationStructural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings
EditorsTomasz Jurdziński, Stefan Schmid
PublisherSpringer Science and Business Media Deutschland GmbH
Pages185-203
Number of pages19
ISBN (Print)9783030795269
DOIs
StatePublished - 2021
Event28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021 - Virtual, Online
Duration: Jun 28 2021Jul 1 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12810 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021
CityVirtual, Online
Period6/28/217/1/21

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Energy
  • Exploration
  • Graph
  • Mobile agent
  • Path
  • Sharing
  • Tree

Fingerprint

Dive into the research topics of 'Graph Exploration by Energy-Sharing Mobile Agents'. Together they form a unique fingerprint.

Cite this