# Computing Tree Structures in Anonymous Graphs via Mobile Agents

arXiv: https://arxiv.org/abs/2506.19365 · HTML: https://mlsanity.com/paper/2506.19365/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 6 of its 39 references that are in the map.
- First posted on arXiv 24 Jun 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 6 of 6)

- [Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs](https://mlsanity.com/paper/1707.05629/) (2017)
- [Run for Cover: Dominating Set via Mobile Agents](https://mlsanity.com/paper/2309.02200/) (2023)
- [Agent-based Leader Election, MST, and Beyond](https://mlsanity.com/paper/2403.13716/) (2024)
- [Efficient Dispersion of Mobile Robots on Graphs](https://mlsanity.com/paper/1805.12242/) (2018)
- [BFS based distributed algorithm for parallel local directed sub-graph enumeration](https://mlsanity.com/paper/2201.11655/) (2022)
- [Near-linear Time Dispersion of Mobile Agents](https://mlsanity.com/paper/2310.04376/) (2023)

## Abstract (arXiv)

Minimum Spanning Tree (MST) and Breadth-First Search (BFS) tree constructions are classical problems in distributed computing, traditionally studied in the message-passing model, where static nodes communicate via messages. This paper investigates MST and BFS tree construction in an agent-based network, where mobile agents explore a graph and compute. Each node hosts one agent, and communication occurs when agents meet at a node. We consider n agents initially dispersed (one per node) in an anonymous, arbitrary n-node, m-edge graph G. The goal is to construct the BFS and MST trees from this configuration such that each tree edge is known to at least one of its endpoints, while minimizing time and memory per agent. We work in a synchronous model and assume agents have no prior knowledge of any graph parameters such as n, m, D, Delta (graph diameter and maximum degree). Prior work solves BFS in O(DDelta) rounds with O(log n) bits per agent, assuming the root is known. We give a deterministic algorithm that constructs the BFS tree in O(min(DDelta, mlog n) + nlog n + Delta log2 n) rounds using O(log n) bits per agent without root knowledge. To determine the root, we solve leader election and MST construction. We elect a leader and construct the MST in O(nlog n + Delta log2 n) rounds, with O(log n) bits per agent. Prior MST algorithms require O(m + nlog n) rounds and max(Delta, log n) log n bits. Our results significantly improve memory efficiency and time, achieving nearly linear-time leader election and MST. Agents are assumed to know λ, the maximum identifier, bounded by a polynomial in n.