Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
From MaRDI portal
Publication:5215469
DOI10.1145/3356883zbMath1473.68119arXiv1805.03476OpenAlexW2980598507MaRDI QIDQ5215469
Max Klimm, Jan Hackfeld, Yann Disser
Publication date: 11 February 2020
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.03476
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Agent technology and artificial intelligence (68T42)
Related Items (11)
An improved lower bound for competitive graph exploration ⋮ Homomorphisms on graph-walking automata ⋮ Pebble guided optimal treasure hunt in anonymous graphs ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Zero-memory graph exploration with unknown inports ⋮ Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ A time to cast away stones ⋮ State complexity of union and intersection on graph-walking automata ⋮ Pebble guided near optimal treasure hunt in anonymous graphs
This page was built for publication: Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
