The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(83)90019-6zbMath0532.68050OpenAlexW4250074066MaRDI QIDQ5896231

David S. Johnson

Publication date: 1983

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(83)90019-6

zbMATH Keywords

puzzlesgamespebble gameblind pursuitdynamic network reliabilitygeneralized dots and boxespartial latin square extendabilitypeeksliding block rearrangeability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem books (00A07)

Related Items (7)

Complexity, appeal and challenges of combinatorial games ⋮ Classifying the computational complexity of problems ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ The complexity of pursuit on a graph ⋮ Complexity of path-forming games ⋮ Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard ⋮ Solitaire automata

This page was built for publication: The NP-completeness column: An ongoing guide