Multi-color pebble motion on graphs

DOI10.1007/s00453-009-9290-7zbMath1202.68280OpenAlexW2016374168MaRDI QIDQ1957647

Gilad Goraly, Refael Hassin

Publication date: 27 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9290-7

zbMATH Keywords

Motion planningPebble motion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Motions of a connected subgraph representing a swarm of robots inside a graph of work stations, Token Swapping on Trees, Reconfiguration of connected graph partitions, Solving simultaneous target assignment and path planning efficiently with time-independent execution, Independent-set reconfiguration thresholds of hereditary graph classes, Introduction to reconfiguration

Cites Work

• The \((n^ 2-1)\)-puzzle and related relocation problems
• A linear-time algorithm for the feasibility of pebble motion on trees
• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Graph puzzles, homotopy, and the alternating group
• Optimal pebble motion on a tree
• Pushing squares around
• A Modern Treatment of the 15 Puzzle
• Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
• The Complexity of Graph Pebbling
• Reconfigurations in Graphs and Grids