Map construction
Agents must not only visit every node but output a map of the anonymous graph, up to isomorphism.
Problem statement and measuresexpand
Agents explore an unknown anonymous port-labelled graph and must output a map: a port-labelled graph, kept in the agent's memory, that is isomorphic to the explored graph (with the ports), with the agent's current node indicated. Time is the number of moves.
Measures: Cost, moves until the map is built.
One agent with a marker
verifiedAn agent with \(k\ge1\) distinct markers it can drop and pick up builds the graph as it explores, in \(O(mn)\) moves.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Timing: asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- Agents: one agent
- A single agent.
- Knowledge: nothing known
- Nothing is known about \(G\).
- Markers: markers
- The agent carries markers it can drop and pick up.
- Whiteboards: no whiteboards
- No whiteboards.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
Results, in order of publication
Introductory and current best recorded here: at most \((5+2/k)mn-3n^2\) plus lower-order moves (equation (4)); a variant that marks both ends of an unexplored edge makes \((3+4/k)mn-n^2\) plus lower-order moves. The bound counts only physical moves; the agent's computation is \(O(n^2m+m^2\log m)\).
Open questions
None recorded for this variant.
Notes
Checked against the full text of Dudek et al. 1991 (a scan, read through OCR). The agent cannot measure distances and has no compass; without markers the problem is unsolvable in general, because regular graphs of the same degree look the same at every node. For directed graphs, one marker and a bound on \(n\) suffice, and without a bound \(\Theta(\log\log n)\) pebbles are necessary and sufficient Bender et al. 2002; Bender et al. also cite the \(O(n\cdot m)\) bound of Dudek et al. for one marker.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.