Pebble guided near optimal treasure hunt in anonymous graphs

DOI10.1007/978-3-030-79527-6_13MaRDI QIDQ2117728zbMATH OpenOpenAlexFDO

Authors Barun Gorain, Kaushik Mondal, Himadri Nayak, Supantha Pandit

Publication date 22 March 2022

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

zbMATH Keywords

mobile agentanonymous graphpebblestreasure hunt

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Recommendations

• Pebble guided optimal treasure hunt in anonymous graphs
• Treasure hunt in graph using pebbles
• Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs
• Treasure hunt with advice
• Undirected Graph Exploration with ⊝(log log n) Pebbles

Cites work

• scientific article; zbMATH DE number 6784996 (Why is no real title available?)
• Advice complexity of treasure hunt in geometric terrains
• Deterministic graph exploration with advice
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• Deterministic treasure hunt in the plane with angular hints
• How many ants does it take to find the food?
• Label-guided graph exploration by a finite automaton
• On the two-dimensional cow search problem
• Online searching with turn cost
• Searching a Tree with Permanently Noisy Advice
• Searching for an axis-parallel shoreline
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• The game of cops and robbers on graphs
• The theory of search games and rendezvous.
• Tight bounds for undirected graph exploration with pebbles and multiple agents
• Yet more on the linear search problem

Cited in

(2)

• Treasure hunt in graph using pebbles
• Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs

This page was built for publication: Pebble guided near optimal treasure hunt in anonymous graphs

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