The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(83)90038-XMaRDI QIDQ4747510zbMATH OpenFDO

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)90038-X

zbMATH Keywords

context-free languagesdiophantine approximationknapsack problemrobot arm reachability

Mathematics Subject Classification ID

Problem books (00A07) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05)

Cited in

(2)

• The complexity of analog computation
• On the embedding of cone graphs in the line with distinct distances between neighbors

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 Q4747510)