Home›Mobile agents on graphs›Exploration›Collaborative exploration›Exploration of dynamic graphs by teams
Exploration of dynamic graphs by teams
An adversary changes the graph over time; how many agents are needed to explore it?
Problem statement and measuresexpand
Agents must visit every node of a dynamic graph: a sequence of graphs \(G_t = (V, E_t)\) on one node set, whose edges are removed round by round by an adversary subject to a connectivity constraint (1-interval connectivity: every \(G_t\) is connected; temporal connectivity: every node can reach every other through edges present at non-decreasing times). The primary measure is the number of agents; the secondary is time in rounds.
Measures: Agents, number of agents needed; Time, rounds.
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
Agents
Time
1-interval-connected rings + connected every round, + undirected, + synchronous, + ring
1 open · 3 results
tight
\(3\) vs \(2\)
adversarial edge changes
unknown
\(3N-6\) vs —
Temporally connected graphs, arbitrary topology any dynamics, + undirected, + synchronous
0 open · 1 results
tight
\(2\eta+1\) vs \(2\eta+1\)
adversarial edge changes
unknown
— vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.