2026-08-05T05:21:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19899 2024-05-31T08:33:44Z ddc:004 open_access

Gathering in Carrier Graphs: Meeting via Public Transportation System Zheng, Haozhi Eguchi, Ryota Ooshita, Fukuhito Inoue, Michiko Gathering Carrier Graph Time-varying Graph Mobile agent The gathering problem requires multiple mobile agents in a network to meet at a single location. This paper investigates the gathering problem in carrier graphs, a subclass of recurrence of edge class of time-varying graphs. By focusing on three subclasses of single carrier graphs - circular, simple, and arbitrary - we clarify the conditions under which the problem can be solved, considering prior knowledge endowed to agents and obtainable online information, such as the count and identifiers of agents or sites. We propose algorithms for solvable cases and analyze the complexities and we give proofs for the impossibility for unsolvable cases. We also consider general carrier graphs with multiple carriers and propose an algorithm for arbitrary carrier graphs. To the best of our knowledge, this is the first work that investigates the gathering problem in carrier graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haozhi Zheng and Ryota Eguchi and Fukuhito Ooshita and Michiko Inoue 2024 Is Part Of LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2024.21 urn:nbn:de:0030-drops-198998 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.21 eng https://creativecommons.org/licenses/by/4.0/legalcode