English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study the problem of treasure hunt in a graph by a mobile agent. The nodesin the graph are anonymous and the edges at any node $v$ of degree $deg(v)$ arelabeled arbitrarily as $0,1,\ldots, deg(v)-1$. A mobile agent, starting from anode, must find a stationary object, called {\it treasure} that is located onan unknown node at a distance $D$ from its initial position. The agent findsthe treasure when it reaches the node where the treasure is present. The {\ittime} of treasure hunt is defined as the number of edges the agent visitsbefore it finds the treasure. The agent does not have any prior knowledge aboutthe graph or the position of the treasure. An Oracle, that knows the graph, theinitial position of the agent, and the position of the treasure, places somepebbles on the nodes, at most one per node, of the graph to guide the agenttowards the treasure.  We target to answer the question: what is the fastest possible treasure huntalgorithm regardless of the number of pebbles are placed?  We show an algorithm that uses $O(D \log \Delta)$ pebbles to find thetreasure in a graph $G$ in time $O(D \log \Delta + \log^3 \Delta)$, where$\Delta$ is the maximum degree of a node in $G$ and $D$ is the distance fromthe initial position of the agent to the treasure. We show an almost matchinglower bound of $\Omega(D \log \Delta)$ on time of the treasure hunt using anynumber of pebbles.

Pebble Guided Near Optimal Treasure Hunt in Anonymous Graphs