Home›Mobile agents on graphs›Computing with agents›BFS tree by agents

BFS tree by agents

\(n\) agents in an anonymous graph must build a breadth-first spanning tree, without being told the root.

Problem statement and measuresexpand

\(n\) agents with distinct identifiers (IDs) are placed on the nodes of an anonymous port-labelled graph with \(n\) nodes, \(m\) edges and maximum degree \(\Delta\). The start is rooted (all agents on one node), dispersed (one agent on each node) or arbitrary. Agents compute only by moving and by talking with agents on the same node. The agents must build a BFS tree from a root they choose, each agent knowing its parent and children: every agent (or node) learns its part of the output. Time is in synchronous rounds; memory in bits per agent.

Measures: Time, rounds; Memory, bits per agent.

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Memory

No assumptions

—

Dispersed start, root unknown + static graph, + undirected, + distinct IDs (eponymous), + local communication, + synchronous, + dispersed start

0 open · 1 results

unknown \(O(\min(D\Delta,m\log n)+n\log n+\Delta\log^2 n)\) vs —

unknown \(O(\log n)\) vs —

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.