Multi-color pebble motion on graphs
From MaRDI portal
Publication:1957647
DOI10.1007/s00453-009-9290-7zbMath1202.68280OpenAlexW2016374168MaRDI QIDQ1957647
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
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