1 Search Results for "Gotfryd, Karol"

Document

DOI: 10.4230/LIPIcs.MFCS.2022.22

Tree Exploration in Dual-Memory Model

Authors: Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering a node, do not receive as input the edge via which they entered. In such model, deterministic memoryless exploration is infeasible, hence the agent needs to be allowed to use some memory. The memory can be located at the agent or at each node. The existing lower bounds show that if the memory is either only at the agent or only at the nodes, then the exploration needs superlinear time. We show that tree exploration in dual-memory model, with constant memory at the agent and logarithmic in the degree at each node is possible in linear time when one of the two additional features is present: fixed initial state of the memory at each node (so called clean memory) or a single movable token. We present two algorithms working in linear time for arbitrary trees in these two models. On the other hand, in our lower bound we show that if the agent has a single bit of memory and one bit is present at each node, then the exploration may require quadratic time even on paths, if the initial memory at nodes could be set arbitrarily (so called dirty memory). This shows that having clean node memory or a token allows linear time exploration of trees in the dual-memory model, but having neither of those features may lead to quadratic exploration time even on a simple path.

Cite as

Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk. Tree Exploration in Dual-Memory Model. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bojko_et_al:LIPIcs.MFCS.2022.22,
  author =	{Bojko, Dominik and Gotfryd, Karol and Kowalski, Dariusz R. and Paj\k{a}k, Dominik},
  title =	{{Tree Exploration in Dual-Memory Model}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.22},
  URN =		{urn:nbn:de:0030-drops-168207},
  doi =		{10.4230/LIPIcs.MFCS.2022.22},
  annote =	{Keywords: Graph exploration, agent, memory, tree, deterministic algorithms, lower bound}
}

Refine by Author
1 Bojko, Dominik
1 Gotfryd, Karol
1 Kowalski, Dariusz R.
1 Pająk, Dominik

Refine by Classification
1 Theory of computation → Graph algorithms analysis
1 Theory of computation → Online algorithms

Refine by Keyword
1 Graph exploration
1 agent
1 deterministic algorithms
1 lower bound
1 memory
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Gotfryd, Karol"

Tree Exploration in Dual-Memory Model

Abstract

Cite as

Thanks for your feedback!

Could not send message