Beyond Rings: Gathering in 1-Interval Connected Graphs


Michail, Othon ORCID: 0000-0002-6234-3960, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179 (2021) Beyond Rings: Gathering in 1-Interval Connected Graphs. PARALLEL PROCESSING LETTERS, 31 (04).

This is the latest version of this item.

[img] Text
main.pdf - Author Accepted Manuscript
Download (639kB) | Preview

Abstract

We examine the problem of gathering $k \geq 2$ agents (or multi-agent rendezvous) in dynamic graphs which may change in every synchronous round but remain always connected ($1$-interval connectivity) [KLO10]. The agents are identical and without explicit communication capabilities, and are initially positioned at different nodes of the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering. We show that only in unicyclic graphs weak gathering is solvable, and we provide a deterministic algorithm for this problem that runs in polynomial number of rounds.

Item Type: Article
Uncontrolled Keywords: Gathering, weak gathering, dynamic graphs, unicyclic graphs, mobile agents
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 01 Nov 2021 09:13
Last Modified: 18 Jan 2023 21:25
DOI: 10.1142/S0129626421500201
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3141844

Available Versions of this Item

Dimensions
Altmetric
CORE (COnnecting REpositories)