Linear-Time Algorithm for Sliding Tokens on Trees

Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein +6

Suppose that we are given two independent sets $I_b$ and $I_r$ of a graph such that $|I_b|=|I_r|$, and imagine that a token is placed on each vertex in $I_b$. Then, the sliding tok…