The \((n^ 2-1)\)-puzzle and related relocation problems
From MaRDI portal
Publication:917310
DOI10.1016/S0747-7171(08)80001-6zbMath0704.68057OpenAlexW2034604437WikidataQ56269529 ScholiaQ56269529MaRDI QIDQ917310
Daniel Ratner, Manfred K. Warmuth
Publication date: 1990
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0747-7171(08)80001-6
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Game theory (91A99) Computing methodologies and applications (68U99) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (45)
Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds ⋮ The transportation problem with conflicts ⋮ Trainyard is NP-hard ⋮ Assembling molecules in ATOMIX is hard ⋮ Weighted \(A^*\) search - unifying view and application ⋮ Kernelization of Cycle Packing with Relaxed Disjointness Constraints ⋮ A linear time algorithm for the feasibility of pebble motion on trees ⋮ A simple proof that the \((n^{2} - 1)\)-puzzle is hard ⋮ Tetravex is NP-complete ⋮ A real-time algorithm for the \((n^{2}-1)\)-puzzle ⋮ SOLVING ABSTRACT COOPERATIVE PATH-FINDING IN DENSELY POPULATED ENVIRONMENTS ⋮ Invitation to combinatorial reconfiguration ⋮ On Complete S-Reachable Graphs ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ The connectivity of token graphs ⋮ Token Swapping on Trees ⋮ Reconfiguration of connected graph partitions ⋮ The Maude strategy language ⋮ Colored pebble motion on graphs ⋮ Sequentially swapping tokens: further on graph classes ⋮ Optimally reordering mobile agents on parallel rows ⋮ Puzzle and dragons is hard ⋮ Computational complexity of jumping block puzzles ⋮ Multi-color pebble motion on graphs ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Unnamed Item ⋮ Motion planning in Cartesian product graphs ⋮ The kissing problem: how to end a gathering when everyone kisses everyone else goodbye ⋮ Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves ⋮ ON mRJ REACHABILITY IN TREES ⋮ \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete ⋮ Independence and matching numbers of some token graphs ⋮ Wooden geometric puzzles: Design and hardness proofs ⋮ On reachability in graphs with obstacles ⋮ Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants ⋮ Pebble exchange group of graphs ⋮ The Fifteen Puzzle—A New Approach ⋮ Computational complexity of jumping block puzzles ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ The edge-connectivity of token graphs ⋮ Twenty years of progress of \(\mathrm{JCDCG}^3\) ⋮ Structural aspects of semigroups based on digraphs ⋮ Pebble exchange on graphs ⋮ Subdimensional expansion for multirobot path planning ⋮ Controlling the learning process of real-time heuristic search
Cites Work
This page was built for publication: The \((n^ 2-1)\)-puzzle and related relocation problems
