On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest

Some simplified NP-complete graph problems

M. R. Garey, David S. Johnson, Larry Stockmeyer · Theoretical Computer Science · 1976 · 2.1K citations

Engineering, Graph Theory, Np-complete Graph Problems +6

Which Problems Have Strongly Exponential Complexity?

Russell Impagliazzo, Ramamohan Paturi, Francis Zane · Journal of Computer and System Sciences · 2001 · 1.3K citations

Strongly Exponential Complexity, Computational Complexity, Time Complexity +2

The Rectilinear Steiner Tree Problem is $NP$-Complete

M. R. Garey, David S. Johnson · SIAM Journal on Applied Mathematics · 1977 · 1.1K citations

Mathematical Programming, Engineering, Graph Theory +15

On the Complexity of k-SAT

Russell Impagliazzo, Ramamohan Paturi · Journal of Computer and System Sciences · 2001 · 996 citations

Engineering, Sat Solving, Computational Complexity +6

A New Algorithm for Generating All the Maximal Independent Sets

Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi et al. · SIAM Journal on Computing · 1977 · 612 citations

Engineering, Combinatorial Design, Network Analysis +17