Search Results

Documents authored by Kanaya, Haruki

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.32
Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Authors: Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. They analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the φ-free graphs, a class that includes every graph with maximum degree at most three and every cactus.
Cite as

Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo. Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.OPODIS.2025.32,
  author =	{Takahashi, Shota and Kanaya, Haruki and Hiraoka, Shoma and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.32},
  URN =		{urn:nbn:de:0030-drops-252052},
  doi =		{10.4230/LIPIcs.OPODIS.2025.32},
  annote =	{Keywords: mobile agents, recolorable graphs, graph exploration}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.37
Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols

Authors: Haruki Kanaya, Ryota Eguchi, Taisho Sasada, and Michiko Inoue

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
The population protocol model is a computational model for passive mobile agents. We address the leader election problem, which determines a unique leader on arbitrary communication graphs starting from any configuration. Unfortunately, self-stabilizing leader election is impossible to be solved without knowing the exact number of agents; thus, we consider loosely-stabilizing leader election, which converges to safe configurations in a relatively short time, and holds the specification (maintains a unique leader) for a relatively long time. When agents have unique identifiers, Sudo {et al. }(2019) proposed a protocol that, given an upper bound N for the number of agents n, converges in O(mNlog n) expected steps, where m is the number of edges. When unique identifiers are not required, they also proposed a protocol that, using random numbers and given N, converges in O(mN²log{N}) expected steps. Both protocols have a holding time of Ω(e^{2N}) expected steps and use O(log{N}) bits of memory. They also showed that the lower bound of the convergence time is Ω(mN) expected steps for protocols with a holding time of Ω(e^N) expected steps given N. In this paper, we propose protocols that do not require unique identifiers. These protocols achieve convergence times close to the lower bound with increasing memory usage. Specifically, given N and an upper bound Δ for the maximum degree, we propose two protocols whose convergence times are O(mNlog n) and O(mNlog N) both in expectation and with high probability. The former protocol uses random numbers, while the latter does not require them. Both protocols utilize O(Δ log N) bits of memory and hold the specification for Ω(e^{2N}) expected steps.
Cite as

Haruki Kanaya, Ryota Eguchi, Taisho Sasada, and Michiko Inoue. Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kanaya_et_al:LIPIcs.OPODIS.2024.37,
  author =	{Kanaya, Haruki and Eguchi, Ryota and Sasada, Taisho and Inoue, Michiko},
  title =	{{Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{37:1--37:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.37},
  URN =		{urn:nbn:de:0030-drops-225734},
  doi =		{10.4230/LIPIcs.OPODIS.2024.37},
  annote =	{Keywords: Population protocols, Leader election, Loose-stabilization, Self-stabilization}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact