Problem
Maximal independent set
An independent set in a graph $G = (V, E)$ is a set $S \subseteq V$ of nodes, no two of which are adjacent. An independent set is maximal (an MIS) if no node can be added to it, that is, every node outside $S$ has a neighbor in $S$.
An MIS of the line graph $L(G)$ is a maximal matching of $G$, and an MIS of $G \times K_{\Delta+1}$ yields a $(\Delta+1)$-coloring of $G$. An MIS is also a $(2,1)$-ruling set and a dominating set.
Runtimes are given in rounds, in terms of the number of nodes $n$, the maximum degree $\Delta$ and the diameter $D$.