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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of deterministically exploring an undirected and initially unknown graph with $n$ vertices either by a single agent equipped with a set of pebbles, or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot be distinguished by the agents, but the edges incident to a vertex have locally distinct labels. The graph is explored when all vertices have been visited by at least one agent. In this setting, it is known that for a single agent without pebbles $Theta(log n)$ bits of memory are necessary and sufficient to explore any graph with at most $n$ vertices. We are interested in how the memory requirement decreases as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. We give tight results for both questions showing that for a single agent with constant memory $Theta(log log n)$ pebbles are necessary and sufficient for exploration. We further prove that the same bound holds for the number of collaborating agents needed for exploration.  the upper bound, we devise an algorithm for a single agent with constant memory that explores any $n$-vertex graph using $mathcal{O}(log log n)$ pebbles, even when $n$ is unknown. The algorithm terminates after polynomial time and returns to the starting vertex. Since an additional agent is at least as powerful as a pebble, this implies that $mathcal{O}(log log n)$ agents with constant memory can explore any $n$-vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph of size $n$ is already $Omega(log log n)$ when we allow each agent to have at most $mathcal{O}( log n ^{1-varepsilon})$ bits of memory for any $varepsilonu003e0$. This also implies that a single agent with sublogarithmic memory needs $Theta(log log n)$ pebbles to explore any $n$-vertex graph.

Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents