TY - GEN
T1 - Tree Exploration in Dual-Memory Model
AU - Bojko, Dominik
AU - Gotfryd, Karol
AU - Kowalski, Dariusz R.
AU - Pająk, Dominik
N1 - Funding Information:
Supported by Polish National Science Centre grant UMO-2019/33/B/ST6/
Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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.
AB - 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.
KW - Graph exploration
KW - agent
KW - deterministic algorithms
KW - lower bound
KW - memory
KW - tree
UR - http://www.scopus.com/inward/record.url?scp=85137576714&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85137576714&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2022.22
DO - 10.4230/LIPIcs.MFCS.2022.22
M3 - Conference contribution
AN - SCOPUS:85137576714
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
A2 - Szeider, Stefan
A2 - Ganian, Robert
A2 - Silva, Alexandra
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022
Y2 - 22 August 2022 through 26 August 2022
ER -