Fetching the paper…

Reading the bibliography…

2013

A Linear Time Algorithm for the Feasibility of Pebble Motion on Graphs

Yu, Jingjin

Original
PDF
Post on X

Understand

Given a connected, undirected, simple graph $G = (V, E)$ and $p \le |V|$ pebbles labeled $1,..., p$, a configuration of these $p$ pebbles is an injective map assigning the pebbles to vertices of $G$.

Let $S$ and $D$ be two such configurations.
From a configuration, pebbles can move on $G$ as follows: In each step, at most one pebble may move from the vertex it currently occupies to an adjacent unoccupied vertex, yielding a new configuration.
A natural question in this setting is the following: Is configuration $D$ reachable from $S$ and if so, how? We show that the feasibility of this problem can be decided in time $O(|V| + |E|)$.

A Linear Time Algorithm for the Feasibility of Pebble Motion on Graphs · Around

Built on

Mathematical Puzzles of Sam Loyd
S. Loyd · 1959
Earlier work this paper cites.
Depth-first search and linear graph algorithms
R. E. Tarjan · 1972
Earlier work this paper cites.

Similar

Graph puzzles, homotopy, and the alternating group
R. M. Wilson · 1974
Cited alongside, same era.
Coordinating pebble motion on graphs, the diameter of permutation groups, and applications
D. Kornhauser, G. Miller, and P. Spirakis · 1984
Cited alongside, same era.
Note on the ‘15’ puzzle
E. W. Story
Cited in the paper.

Then

A linear-time algorithm for the feasbility of pebble motion on trees
V. Auletta, A. Monti, M. Parente, and P. Persiano · 1999
Later among the works it cites.
Multi-color pebble motion on graph
G. Goraly and R. Hassin · 2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…