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.
Temporally connected graphs, arbitrary topology
verifiedPerpetual exploration of a temporally connected graph with \(\eta\) transient edges needs exactly \(2\eta+1\) agents.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: any dynamics
- A temporal graph is a sequence \(\mathcal G=(G_t)_{t\ge 0}\) with \(G_t=(V,E_t)\) on a fixed node set. It is temporally connected if for all \(u,v\in V\) and every time \(t\) there is a journey (a path whose edges appear at non-decreasing times \(\ge t\)) from \(u\) to \(v\). No \(G_t\) need be connected.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- \(2\eta\) agents fail even with identifiers, knowledge of \(n\) and \(k\), and unbounded whiteboards
Results, in order of publication
Introductory and current best; whiteboards of \(O(\log\deg(v))\) bits at node \(v\).
Open questions
None recorded for this variant.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.