Treasure hunt in graph using pebbles

DOI10.1007/978-3-031-21017-4_7MaRDI QIDQ6155238zbMATH OpenOpenAlexFDO

Authors Adri Bhattacharya, Barun Gorain, P. S. Mandal

Publication date 12 June 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.00857

zbMATH Keywords

mobile agentdeterministic algorithmsanonymous graphpebblestreasure hunt

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: In this paper, we study the treasure hunt problem in a graph by a mobile agent. The nodes in the graph $G=(V,E)$ are anonymous and the edges incident to a vertex $vinV$ whose degree is $deg(v)$ are labeled arbitrarily as $0,1,ldots,deg(v)-1$. At a node $t$ in $G$ a stationary object, called {it treasure} is located. The mobile agent that is initially located at a node $s$ in $G$, the starting point of the agent, must find the treasure by reaching the node $t$. The distance from $s$ to $t$ is $D$. The {it time} required to find the treasure is the total number of edges the agent visits before it finds the treasure. The agent does not have any prior knowledge about the graph or the position of the treasure. An oracle, that knows the graph, the initial position of the agent, and the position of the treasure, places some pebbles on the nodes, at most one per node, of the graph to guide the agent towards the treasure. This paper aims to study the trade-off between the number of pebbles provided and the time required to find the treasure. To be specific, we aim to answer the following question. ``What is the minimum time for treasure hunt in a graph with maximum degree $Delta$ and diameter $D$ if $k$ pebbles are placed? " We answer the above question when $k<D$ or $k=cD$ for some positive integer $c$. We design efficient algorithms for the agent for different values of $k$. We also propose an almost matching lower bound result for $k<D$.

Recommendations

• Pebble guided optimal treasure hunt in anonymous graphs
• Pebble guided near optimal treasure hunt in anonymous graphs
• Pebbling graphs
• Pebble game algorithms and sparse graphs
• scientific article; zbMATH DE number 1040545
• Minesweeper on graphs
• Pebble exchange on graphs
• General graph pebbling
• Graph searching games

Cites work

• Advice complexity of treasure hunt in geometric terrains
• Communication algorithms with advice
• Deterministic treasure hunt in the plane with angular hints
• Drawing maps with advice
• Pebble guided optimal treasure hunt in anonymous graphs
• Reaching a target in the plane with no information

Cited in

(6)

• Deterministic treasure hunt in the plane with angular hints
• Advice complexity of treasure hunt in geometric terrains
• Collision-free exploration by mobile agents using pebbles
• On time-travel planning in dynamic graphs
• Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
• Treasure hunt with advice

This page was built for publication: Treasure hunt in graph using pebbles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6155238)