DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2024.21

Gathering in Carrier Graphs: Meeting via Public Transportation System

Authors: Haozhi Zheng, Ryota Eguchi, Fukuhito Ooshita, and Michiko Inoue

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract

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.

Cite as

Haozhi Zheng, Ryota Eguchi, Fukuhito Ooshita, and Michiko Inoue. Gathering in Carrier Graphs: Meeting via Public Transportation System. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.SAND.2024.21,
  author =	{Zheng, Haozhi and Eguchi, Ryota and Ooshita, Fukuhito and Inoue, Michiko},
  title =	{{Gathering in Carrier Graphs: Meeting via Public Transportation System}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.21},
  URN =		{urn:nbn:de:0030-drops-198998},
  doi =		{10.4230/LIPIcs.SAND.2024.21},
  annote =	{Keywords: Gathering, Carrier Graph, Time-varying Graph, Mobile agent}
}

Search Results

Documents authored by Zheng, Haozhi

Gathering in Carrier Graphs: Meeting via Public Transportation System

Abstract

Cite as

Thanks for your feedback!

Could not send message