The NP-completeness column: An ongoing guide

1987/06/01 by David S. Johnson, David S Johnson · 7 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Protein Degradation and Inhibitors

paper · doi:10.1016/0196-6774(87)90043-5

crossref issued 1987/06/01 · crossref published 1987/06/01 · crossref published-print 1987/06/01 · openalex publication_date 1987/06/01 · crossref created 2004/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06 · crossref deposited 2026/04/30 · crossref indexed 2026/05/12

Citations

• Linear Programming in Linear Time When the Dimension Is Fixed
• Factoring polynomials with rational coefficients
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited by

• On search decision and the efficiency of polynomial-time algorithms
• The Nature of Computation
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Nonconstructive tools for proving polynomial-time decidability
• Constructive results from graph minors: linkless embeddings
• Graph minor [wikipedia]
• P versus NP problem [wikipedia]