The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(83)90019-6MaRDI QIDQ5896231zbMATH OpenOpenAlexFDO

Authors D. 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

blind pursuitdynamic network reliabilitygamesgeneralized dots and boxespartial latin square extendabilitypebble gamepeekpuzzlessliding block rearrangeability

Mathematics Subject Classification ID

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

Recommendations

• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide

Cited in

(11)

• Solitaire automata
• Complexity of path-forming games
• Complexity, appeal and challenges of combinatorial games
• Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard
• Classifying the computational complexity of problems
• Fine-grained Lower Bounds on Cops and Robbers
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The complexity of pursuit on a graph

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896231)