Home›Mobile agents on graphs›Computing with agents›Maximal independent set by agents

Maximal independent set by agents

\(n\) agents in an anonymous graph must mark a maximal independent set of nodes.

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 settle on the nodes of a maximal independent set, every other agent knowing it is not in the set: 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

—

No knowledge + static graph, + undirected, + distinct IDs (eponymous), + local communication, + synchronous

0 open · 2 results

unknown \(O(\max\{n\log^2 n,m\})\) vs —

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

Knowing \(n\) and \(\Delta\) + knows \(n\), \(\Delta\)

0 open · 2 results

unknown \(O(n\log^2 n+D\Delta\log 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.