A list of books and papers I’ll reference as I discuss the problems.

Books:

• Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  New York:W.H. Freeman and Company, 1979.
• Elwyn R. Berlekamp, John H. Conway, Richard K. Guy.  Winning Ways for Your Mathematical Plays, Vol 1.  A.K. Peters, 2001.
• Eric Bach and Jeffrey Shallit. Algorithmic Number Theory Vol 1: Efficient Algorithms.   MIT Press, 1996.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,  Clifford Stein.  Introduction to Algorithms (3e).  MIT Press, 2009.
• John E. Hopcroft and Jeffrey D. Ullman.  Introduction to Automata Theory, Languages, and Computation.  Addison-Wesley, 1979.
• Harry R. Lewis and Christos H. Papadimitriou.  Elements of the Theory of Computation (2e).  Prentice-Hall, 1998.
• John C. Martin. Introduction to Languages and the Theory of Computation (4e).  McGraw Hill. 2011.
• Bernard Moret. The Theory of Computation. Addison-Wesley (1e). 1998.
  
• Stuart Russell and Peter Norvig.  Artificial Intellligence: A Modern Approach (3e). Prentice Hall, 2010.

Papers: (with links, where available.  Some of these papers are slightly different than ones referenced in the G&J book, because these are the references I found.):

• H.M. Abdel-Wahab. Scheduling with Applications to Register Allocation and Deadlock Problems, Doctoral Thesis, Dept. of Electrical Engineering, University of Waterloo, Waterloo, Ontario. 1976.
• A.V. Aho, S.C. Johnson and J.D. Ullman.  Code Generation for Expressions with Common Subexpressions.  Journal of the ACM, Vol 24, No. 1, pp. 146-160.  1977.
• A.V. Aho, Y. Sagiv, and J.D. Ullman.  Equivalences Among Relational Expressions.  SIAM J. Computing.  Vol 8, No, 2, pp. 218-246.  1979.
• Greg Aloupis, Erik D. Demaine, Alan Guo, Giovanni Viglietta.  Classic Nintendo Games are (Computationally) Hard.  Springer Lecture Notes in Computer Science vol. 8496 (Fun With Algorithms) pp. 40-51. 2015.
• Dana Anglin.  On the Complexity of Minimum Inference of Regular Sets.  Information and Control, Vol 39, Issue 3.  pp. 337-350.  1978.
• Toshiro Araki, Yuji Sugiyama, Tadao Kasami, and Jun Okui.  Complexity of the Deadlock Avoidance Problem.  Proceedings of the 2nd IBM Symposium on Mathematical Foundations of Computer Science.  pp. 229-252.  1977.  (It’s worth mentioning that the link here is to a draft, or possibly a technical report of the paper that has some pages in the middle missing.  But it’s all I could find)
• Lewis Denver Baxter.  The Complexity of Unification. PhD Thesis, The University of Waterloo.  1977.
• Catriel Beeri and Philip A. Bernstein.  Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Transactions on Database Systems, Vol. 4, No. 1, March 1979. pp 30-59.
• Elwyn R. Brelekamp, Robert J. McEliece, and Henk C.A. van Tilborg. On the Inherent Intractability of Certain Coding Problems.  IEEE Transactions on Information Theory Vol IT-24, No. 3.  pp. 384-386.  May, 1978.
• Piotr Berman and Georg Schnitger. On the complexity of Approximating the Independent Set Problem.  Information and Computation, vol 96, issue 1, pages 77-74.  1992.
• Ronald V. Book.  On Languages Accepted in Polynomial Time.  SIAM Journal of Computing Vol 1 No 4. pp. 281-287. 1972.
• Ronald V. Book and Sheila A. Greibach.  Quasi-Realtime Languages. Mathematical Systems Theory 4, pp 97-111.  1970.
• K.S. Booth.  PQ-Tree Algorithms.  Doctoral Thesis, Dept of Electrical Engineering and Computer Science, University of California, Berkeley, 1975.
• A.E. Brouwer and H.J. Veldman. Contractaibility and NP-Completeness.  J. Graph Theory 11 (1987) no 1, 71-79.
• P. Brucker.  On the Complexity of Clustering Problems.  Optimization and Optimization Research, Lecture Notes in Econoics and Mathematical Systems, Springer.  pp. 45-54. 1978.
• Peter Brucker, M.R. Garey, D.S. Johnson.  Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness.  Mathematics of Operations Research. Vol 2, No. 3, pp. 275-284.  1977.
• John Bruno and Peter Downey.  Complexity of Task Sequencing with Deadline, Set-up Times, and Changeover Costs.  SIAM J. Computing, Vol. 7, No. 4, pp. 393-404.  1978.
• John Bruno and Ravi Sethi.  Code Generation for a One-Register Machine.  Journal of the ACM, Vol 23, No. 3.  pp. 502-510. 1976.
• Christina Büsing and Sebastian Stiller. Line Planning, Path Constrained Network Flow and Inapproximability.  Networks 57(1), pp. 106-113. 2010.
• Ashok. K. Chandra and Philip M. Martin.  Optimal Implementation of Conjunctive Queries in Relational Data Bases.  Proceedings of the 9th  Annual ACM Symposiom on Theory of Computing.  pp. 77-90.  1977.
• V. Chvátal.  Recognizing Intersection Patterns. Annals of Discrete Mathematics.  Vol 8. pp.249-251.  1980.
• Václaw Chvátal and Peter Hammer.  Aggregation of Inequalities in Integer Programming.  Annals of Discrete Mathematics 1(1977) pp. 145-162.
• V. Chvátal and C. Thomassen.  Distances in Orientations of Graphs.  Journal of Combinatorial Theory, Series B. Vol 24(1), pp. 61-75. 1978.
• F.R.K. Chung.  On a Ramsey-type Problem.  J. Graph Theory 7 (1983), no. 1, 79–83.
• R.A. Cody and R.G. Coffman Jr.  Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices.  J.ACM Vol 23, No 1. pp. 103-115. 1976.
• Douglas Comer and Ravi Sethi.  The Complexity of Trie Index Construction.  J.ACM Vik 24, No, 3, pp. 4280440.  1977.
• Harold E. Conn and Joseph O’Rourke.  Some Restricted Rectangle Covering Problems.  Johns Hopkins University Department of Computer Science.  Report JHU-97/13.  1987.
• Robert Constable, Harry Hunt III, Sartaj Sahni.  On the Computational Complexity of Scheme Equivalence.  TR 74-201, Department of Computer Science, Cornell University.  1974.
• Stephen A. Cook.  The Complexity of Theorem-Proving Procedures.  Proceedings of the Third Annual Symposium on Theory of Computing. pp. 151-158.  1971.
• David P. Dobkin and Steven P. Reiss.  The Complexity of Linear Programming.  Theoretical Conputer Science 11 (1980) pp.1-11.
• Peter J. Downey and Ravi Sethi.  Assignment Commands and Array Structures.  Proceedings of the 17th Annual Symposium on Foundations of Computer Science. pp. 57-66. 1976.
• Kapali P. Eswaran and R. Endre Tarjan.  Augmentation Problems.  SIAM J. Computing. Vol 5, No 4, pp 653-665. 1976.
• S. Even, A. Itai, and A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems.  SIAM J. Computing, Vol 5, No. 4, pp.691-703. 1976.
• S. Even and Y. Shiloah. NP-Completeness of Several Arrangement Problems. Technical Report No. 43, Israel Institute of Technology, Department of Computer Science.  January, 1975.
• Shimon Even and R. Endre Tarjan. A Combinatorial Problem Which is Complete in Polynomial Space.  Proceedings of the seventh annual ACM symposium on Theory of computing.  pp. 66-71. 1975.
• M. Florian, J.K. Lenstra, and A.H.G. Rinnooy Kan.  Deterministic Production Planning: Algorithms and Complexity.   Journal of Management Science. Vol. 26, No. 7.  pp. 669-679. 1980.
• Steven Fortune, John Hopcroft, and Erik Meineche Schmidt.  The Complexity of Equivalence and Containment for Free Single Variable Program Schemes. TR77-310. Department of Computer Science, Cornell University. 1977
• A.S. Fraenkel, M.R. Garey, D.S. Johnson, T. Schaefer, and Y. Yesha.  The Complexity of Checkers on an NxN Board- Preliminary Report. Proceedings of the 19th Annual Symposium on the Foundations of Computer Science. pp. 55-64. 1978.
• A.S. Fraenkel and Y. Yesha.  Complexity of Problems in Games, Graphs, and Algebraic Equations. Discrete Applied Mathematics 1(1979)15-30.
• Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim. Approximation Algorithms for Some Routing Problems.  SIAM J. Computing. Vol 2, No 2. May 1979.
• Zvi Galil. Hierarchies of Complete Problems.  Acta Informatica 6, pp. 77-88.  1976.
• Zvi Galil and Nimrod Megiddo.  Cyclic Ordering is NP-Complete.  Theoretical Computer Science Vol 5, pp. 179-182. 1977.
• M.R. Garey and D.S. Johnson.  Complexity Results for Multiprocessor Scheduling Under Resource Constraints.  SIAM J. Computing.  Vol 4, No. 4, pp. 397-411.  1975.
• M.R. Garey, R.L. Graham, and D.S. Johnson.  Some NP-Complete Geometric Problems.  STOC76, pp 10-22. 1976.
• M.R. Garey, R.L. Graham, and D.S. Johnson. The Complexity of Computing Steiner Minimal Trees.  SIAM J. Appl. Math. 32(4), pp 835-859.  1977.
• M.R.Garey, R.L. Graham, D.S. Johnson, and D.E. Knuth.  Complexity Results for Bandwidth Minimization.  SIAM Journal on Applied Mathematics.  Vol 34, No. 3. pp 477-495. 1978
• M.R. Garey and D.S.Johnson.  Complexity results for multiprocessor scheduling under resource constraints.  SIAM Journal of Computing, Vol 4, No 4, pp. 397-411.
• M.R. Garey, D.S. Johnson, G.L. Miller, and C.H. Papadimitriou.  The Complexity of Coloring Circular Arcs and Chords.  SIAM Journal on Algebraic and Discrete Methods. Vol 1., No. 2, pp. 216-227.  1980.
• M.R. Garey, D.S. Johnson, and Ravi Sethi.  The Complexity of Flowshop and Jobshop Scheduling.  Mathematics of Operations Research Vol 1, No. 2. pp. 117-129.  May 1976.
• M.R.Garey, D.S. Johnson and L. Stockmeyer.  Some Simplified NP-Complete Problems.STOC ’74. pages 47-63. 1974.
• Fanica Gavril. Some NP-Complete Problems on Graphs.  Proceedings of the 1977 Conference on Information Sciences and Systems.  pages 91-95.  1977.
• James F. Gimpel. A Method of Producing a Boolean Function Having an Arbitrarily Prescribed Prime Implicant Table.  IEEE Transactions on Electronic Computers. 14, pp. 485-488.  1965.
• Michael Goemans.  Advanced Combinatorial Optimization Lecture Notes: Lecture 10.  Massachusetts Institute of Technology.  2009.
• E. Mark Gold.  Complexity of Automation Identification from Given Data. Information and Control 37, pp. 302-320.  1978.
• Teofilo Gonzalez and Sartaj Sahni.  Open Shop Scheduling to Minimize Finish Time.  Journal of the ACM, Vol 23, No. 4. pp. 665-679.  1976.
• Sheila A. Greibach.  The Hardest Context-Free Language.  SIAM J. Computing Vol 2, No 4. pp. 304-310. 1973.
• Michael A. Harrison, Walter L. Ruzzo ad Jeffrey D. Ullman. Protection in Operating Systems.  Communications of the ACM Vol 19, No. 8. pp. 461-471. 1976.
• Harry Bowen Hunt III.  On the Time and Tape Complexity of Languages.  PhD Thesis, Cornell University.  1973.
• Harry B. Hunt III, Daniel J. Rosenkrantz, and Thomas G. Szymanski.  On the Equivalence, Containment, and Covering Problems for the Regular and Context-Free Languages.  Journal of Computer and System Sciences Vol 12, pp. 222-268. 1976.
• Harry B. Hunt III, Thomas G. Szymanski, and Jeffrey D. Ullman.  On the Complexity of LR(K) Testing.  Communications of the ACM Vol 18, No. 12. pp. 707-716.  1975.
• Laurent Hyafil and Ronald L. Rivest.  Constructing Optimal Binary Decision Trees is NP-Complete.  Information Processing Letters Vol 5, No. 1,  pp. 15-17.  1976.
• Toshihide Ibaraki.  Approximate Algorithms for the Multiple-Choice Continuous Knapsack Problems.  Journal of the Operations Research Society of Japan. Vol 23, No. 1.  pp. 28-63. 1980.
• Toshihide Ibaraki, Tsunehiko Kameda, and Shunichi Toida.  NP-Complete Diagnosis Problems on System Graphs.  Transactions of the IECE of Japan. Vol E 62, No 2. pp 81-88. 1979.
• Oscar H. Ibarra and Sartaj K. Sahni.  Polynomially Complete Fault Detection Problems.  IEEE Transactions on Computers.  Volume C-24, No. 3. pp. 242-249. 1975.
• Alon Itai. Two-Commodity Flow. Journal of the Association for Computing Machinery.  Vol 25, No. 4. pp. 596-611.  1978.
• A. Itai, Y. Perl, and Y. Shiloach.  The Complexity of Finding Maximum Disjoint Paths with Length Constraints.  Networks, Vol 12 (1982), pp. 277-286.
• Alon Itai, Michael Rodeh, and Steven L. Tanimoto.  Some Matching Problems for Bipartite Graphs.  Journal of the ACM. Vol 25, No 4, pp. 517-525.  1978.
• R. Jeroslow.  Bracketing Discrete Problems by Two Problems of Linear Optimization.  Proceedings of the First Symposium on Operations Research (at Heidelberdg). pp. 205-216.  1976.
• David S. Johnson. The NP-Completeness Column: An Ongoing Guide.  Journal of Algorithms Vol 8, No 3, pp. 438-448.  1987.
• Donald Johnson and Samuel Kashdan. Lower Bounds for Selection in X+Y and Other Multisets.  Journal of the Association for Computing Machinery. Vol 25, No 4, pp556-570.  1978.
• D.S. Johnson, J.K. Lenstra, and A.H.G Rinnooy Kan. The Complexity of the Network Design Problem.  Networks, Vol 8(1978) pp. 279-285.  1978.
• Donald B. Johnson and Tetsuo Mizoguchi.Selecting the Kth Element in X+Y and X1+X2+…+Xm”. Siam J. Computing, Vol 2, No. 7, pp. 147-153. 1978.
• D.S. Johnson and K.A. Niemi.  On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees.  Mathematics of Operations Research.  Vol 8, No. 1.  pp. 1-14. 1983.
• D.S. Johnson and F.P. Preparata.  The Densest Hemisphere Problem.  Theoretical Computer Science, Vol. 6, No. 1, pp. 93-107.  1978.
• Neil D. Jones, Lawrence Landweber, Y. Edmund Lien.  Complexity of Some Problems in Petri Nets.  Theoretical Computer Science Vol. 4, pp. 277-299. 1977.
• Neil D. Jones and Sven Skyum.  Complexity of Some Problems Concerning L Systems.  Mathematica Systems Theory Vol 13, pp. 29-43. 1979.
• O. Kariv and S.L. Hakimi.  An Algorithmic Approach to Network Location Problems. I: The p-centers.  SIAM J. Applied Math, Vol 37 No 3, December 19. 79.
• O. Kariv and S.L. Hakimi.  An Algorithmic Approach to Network Location Problems, II: The pmedians.  SIAM J. Applied Math, Vol 37, No 3, pp. 539-560. December 1979.
• Haim Kaplan and Ron Shamir. The Domatic Number Problem on Some Perfect Graph Families. Information Processing Letters Vol 49, pages 51-56.  1995.
• Richard M. Karp.  Reducibility Among Combinatorial Problems.  In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103
• Toshinobu Kashiwabara and Toshio Fujisawa.  An NP-Complete Problem on Interval Graph.  Proceedings of 1979 ISCAS. pages 82-83.
• Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld.  Landmarks in Graphs.  Discrete Applied Mathematics 70(1996) 217-229.
• Lawrence T. Kou.  Polynomial Complete Consecutive Information Retrieval Problems.  SIAM J. Computing. Vol 6, No. 1.  March 1977 pp. 67-75. 1977.
• L.T. Kou, L.J. Stockmeyer, and C.W. Wong. Covering Edges by Cliques with Regard to Keyword Conflicts and Intersection Graphs. CACM Vol 21, No 2. pages 135-139. 1978.
• M.S.Krishnamoorthy.  An NP-Hard Problem in Bipartite Graphs. SIGACT News, January 1975, page 26.
• M.S. Krishnamoorthy and N. Deo. Complexity of the Minimum-Dummy-Activities Problem in a Pert Network. Networks, Vol 9 (1979). pp 189-194.
• Dexter Kozen.  Complexity of Finitely Presented Algebras.  Proceedings of the Ninth Annual Symposium on the Theory of Computing.  pp. 164-177.  1977.
• Dexter Kozen. First Order Predicate Logic Without Negation is NP-Complete.  TR 77-307. Department of Computer Science, Cornell University. 1977.
• Dexter Kozen.  Lower Bounds for Natural Proof Systems.  Proceedings of the 18th Symposium of the Foundations of Computer Science.  pp. 254-266.  1977.
• N.D. Jones and S.S. Muchnick.  Even Simple Programs are Hard to Analyze.  Journal of the ACM Vol 24. No. 2. pp. 338-350.  April 1977.
• Richard E. Ladner.  The Computational Complexity of Provability in Systems of Modal Propositional Logic.  SIAM J. Computing Vol 6, No. 3.  1977.
• Eugene L. Lawler.  A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness. Annals of Discrete Mathematics. 1, pp. 331-342.  1977.
• E.L. Lawler.  Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints.  Annals of Discrete Mathematics Vol 2, pp. 75-90.  1978.
• Jan van Leeuwen.  The Membership Question for Et0L-Languages is Polynomially Complete.  Information Processing Letters, Volume 3, number 5. pp. 138-143. 1975.
• Jan van Leeuwen.  Having a Grundy-Numbering is NP-Complete.  Technical Report #207.  Pennsylvania State University Computer Science Dept.  1976.
• J.K. Lenstra, A.H.G Rinnooy Kan, and P. Brucker.  Complexity of Scheduling Problems.  Annals of Discrete Mathematics 1, pp. 343-362.  1977.
• David Lichtenstein.  Planar Formulae and Their Uses. SIAM J. Computing. Vol 11, No. 2. pp 329-343.  1982.
• David Lichtenstein and Michael Sipser.  Go is Polynomial-Space Hard. Journal of the Association for Computing Machinery, Vol. 27, No. 2, pp. 393-401. 1980.
• Andrew Lim.  An Effective Ship Berthing Algorithm.  Proceedings of the 16th International Joint Conference on Artificial Intelligence. pp. 594-597.  1999.
• W. Lipski Jr. One More Polynomial Complete Consecutive Retrieval Problem.  Information Processing Letters. Vol 6, No. 3. pp. 91-93. June, 1977.
• Witold Lipski Jr. Generalizations of the Consecutive Ones Property and Related NP-Complete Problems.  Coordinated Science Laboratory Report no. T-067, University of Illinois.  2015 (This is the issue date of the link, I’m sure it was written much earlier).
• Leonard Lipschitz.  Some remarks on the Diophantine Problem for Addition and Divisibility. Bulliten de la Societe mathematique do Belgique. Serie B.  pp. 41-52.  1981.
• P.C. Liu and R.C. Geldmacher. On the deletion of nonplanar edges of a graph. Proc 10th SE Conf.Combinatorics, Graph Theory, and Computing.  pp. 727-738.  1978.
• Errol Lynn Lloyd.  On Triangulations of a Set of Points in the Plane.  Proc. 18th Annual Symposium on Foundations of Computer Science. pp. 228-240. 1978.
• Claudio L. Lucchesi and Sylvia L. Osborn.  Candidate Keys for Relations.  Journal of Computer and System Sciences 17, pp. 270-279.  1978.
• George S. Lueker.  Two NP-Complete Problems in Nonnegative Integer Programming.  Technical Report TR-178 Computer Science Laboratory, Department of Electrical Engineering, Princeton University.  1975.
• Yasuko Matsui and Tomomi Matsui.  NP-Completeness for calculating power indices of weighted majority games.  Theoretical Computer Science 263, pp. 305-310.  2001.
• S. Maheshwari.  Travel marker placement problems are NP-Complete.  Report Np. CU-CS-092-76.  Dept of Computer Science, University of Colorado. 1976.
• David Maier.  The Complexity of Some Problems on Subsequences and Supersequences.  J.ACM, Vol 25, No. 2, pp. 322-336. 1978.
• David Maier and James A Storer. A note on the complexity of the superstring problem. Technical Report 233, Princeton University Dept of Electrical Engineering and Computer Science. 1977.
• Kenneth L. Manders and Leonard Adleman.  NP-Complete Decision Problems for Binary Quadratics.  Journal on Computer and System Sciences 16, pp. 168-184.  1978.
• H.A. Maurer, A. Saolmaa, and D. Wood.  ET0L Forms. Journal of Computer and System Sciences 16, pp. 345-371. 1978.
• Tadao Murata.  Petri Nets: Properties, Analysis, and Applications.  Proceedings of the IEEE, Vol 77, No. 4, pp. 541-580.  1989.
• Katta G. Murty.  A Fundamental Problem in Linear Inequalities with Applications to the Travelling Salesman Problem.  Mathematical Programming 2, pp. 296-308.  1972.
• Giorgi Nadiradze.  Bounded Diameter Minimum Spanning Tree.  Master’s Thesis, Central European University,  2013.
• J. Nešetril and A. Pultr.  A Dushnik-Miller Type Dimension of Graphs and its Complexity.  Proceedings of the 1977 International FCT-Conference.  pp 482-493. 1977.
•  James Orlin. Contentment in Graph Theory: Covering Graphs with cliques. Proceedings of the Koninklijke Nederlandae Akademie van Wetenschappen, Series A, vol 80(5). 1977.
• J. Opatrny. Total Ordering Problem.  SIAM Journal of Computing. Vol 8, No 1. pp. 111-114. 1979.
• Christos H. Papadimitriou.  On the Complexity of Edge Traversing. Journal of the Association for Computing Machinery.  Vol 23, No 3, pp 544-554. 1976.
• Christos H. Papadimitriou.  The Adjacency Relation on the Traveling Salesman Polytope is NP-Complete.  Mathematical Programming Vol 14, pp. 312-324.  1978.
• C. H. Papadimitriou.  The Complexity of the Capacitated Tree Problem.  Networks, Vol 8 (1978) 217-230.  1978.
• C.H.Papadimitriou.  The Euclidean Traveling Salesman Problem is NP-Complete.  Theoretical Computer Science 4(1977) 237-244.  1977.
• Ch. H. Papadimitriou.  The NP-Completeness of the Bandwidth Minimization Problem. Computing 16, pages 263-270. 1976.
• Christos H. Papadimitriou, Philip A. Bernstein, and James B. Rothnie.  Some Computational Problems Related to Database Concurrency Control.  Proc. Conf. On Theoretical Computer Science, University of Waterloo, Waterloo, Ontario, pp. 275-282.  1977.
• Christos H. Papadimitriou and Paris C. Kaellakis.  Flowshop Scheduling with Limited Temporary Storage.  Journal of the Association for Computing Machinery, Vol 21, No. 3. pp. 533-549.  July, 1980.
• M.S. Paterson and A.A. Razborov.  The Set of Minimal Braids is Co-NP-Complete.  Journal of Algorithms Vol 12, pp. 393-408.  1991.
• Charles P. Pfleeger.  State Reduction in Incompletely Specified Finite-State Machines.  IEEE Transactions on Computers Vol 22, Issue 12.  pp. 1099-1102. 1973.
• David A. Plaisted.  Some Polynomial and Integer Divisibility Problems are NP-Hard.  Proceedings of the 18th Annual Symposium on Foundations of Computer Science.  pp. 264-267. 1976.
• David A. Plaisted.  New NP-Hard and NP-Complete Polynomial and Integer Divisibility Problems.  Theoretical Computer Science 31, pp. 125-138.  1984.
• David Alan Plaisted. Sparse Polynomials and Polynomial Reducibility.  Journal of Computer and System Sciences Vol 14, pp. 210-221. 1977.
• V.R. Pratt. Two Easy Theories Whose Combination is Hard.  MIT Technical Report. 1977.
• Pavel Pudlak. Polynomially Complete Problems in the Logic of Automated Discovery. Proceedings of the 4th Symposium on the Mathematical Foundations of Computer Science.  pp. 358-361. 1975.
• Pavel Pudlak and F.N. Springsteel.  Complexity in Mechanized Hypothesis Formation.  Theoretical Computer Science 8, pp. 203-223.  1979.
• C.V. Ramamoorthy, K.H. Kim, and W.T. Chen.   Optimal Placement of Software Monitors Aiding Systematic Testing.  IEEE Transactions on Software Engineering, Vol SE-1, No. 4. pp. 403-411.  1975.
• Steven Peter Reiss.  Inverse Translation: The Theory of Practical Automatic Programming.  Doctoral Thesis, Yale University.  1977.
• Steven P. Reiss.  Statistical Database Confidentiality.  Report No. 25, Department of Statistics, University of Stockholm.  1977.
• Edward L. Robertson.  Code Generation for Short/Long Address Machines. Report No. 1779, Mathematics Research Center, University of Wisconsin, Madison.  1977.
• Edward L. Robertson. Microcode Bit Optimization is NP-Complete. IEEE Transactions on Computers, Vol C-28 No. 4. pp. 316-319. April, 1979.
• Donald J Rose and Robert Endre Tarjan.  Algorithmic Aspects of Vertex Elimination on Directed Graphs. SIAM Journal on Applied Mathematics Vol 34, No 1.  pp 176-197. 1978.
• A. Rosenthal.  Computing Reliability of Complex Systems.  Doctoral Thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, CA 1974.
• D.J. Rosentrantz and H.B. Hunt III.  Testing for Grammatical Coverings.  Theortetical Computer Science 38, pp.323-341.  1985.
• A Rosenthal.Computing the Reliability of Complex Networks.  SIAM J. Appl. Math Vol 32, No 2, 1977. pp. 384-393.
• Senjuti Basu Roy, Laks V.S. Lakshmanan, Rui Liu.  From Group Recommendations to Group Formation.  Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.  pp. 1603-1616. 2015.
• Sartaj Sahni. Computationally Related Problems.  SIAM J. Computing Vol 3, No 4. 1974.
• Sartaj Sahni and Teofilo Gonzalez.  P-Complete Approximation Problems.  JACM 23(3) pp.555-565. 1976.
• T.J. Schaefer. The complexity of satisfiability problems, Proceedings of the 10th annual ACM Symposium on Theory of Computing, pages 216-226. 1978.
• Thomas J. Schaefer.  On the Complexity of Some Two-Person Perfect-Information Games. Journal of Computer and System Sciences Vol 16, pp. 185-225. 1978.
• Ravi Sethi.  A Note on Implementing Parallel Assignment Instructions.  Information Processing Letters Vol 2, pp. 91-95. 1973.
• Ravi Sethi.  Complete Register Allocation Problems.  SIAM J. Computing Vol4 No. 3, pp. 226-246. September 1977.
• E. Shamir and C. Beeri.  Checking Stacks and Context-Free Programmed Grammars Accept p-complete Languages.  Proceedings of ICALP 1974, pp. 27-33. 1974.
• Michael Ian Shamos.  Geometry and Statistics: Problems at the Interface.  in Algorithms and Complexity: New Directions and Recent Results. Academic Press, New York. pp. 251-280.  1976.
• R. Statman.  Complexity of Derivations From Quantifier-Free Horn Formulae, Mechanical Introduction of Explicit Definitions, and Refinement of Completeness Theorems.  Proceedings of Logic Colloquium 76. pp 505-518. 1976.
• Iain A. Stewart. Deciding whether a planar graph has a cubic subgraph is NP-complete.  Discrete Mathematics 126(1994).  pp. 349-357.
• L.J. Stockmeyer.  The Set Basis Problem is NP-Complete.  IBM Technical Report RC-5431.  1975.
• L.J. Stockmeyer and A.B. Meyer.  Word Problems Requiring Exponential Time: Preliminary Report. Proceedings of the Fifth Annual Symposium on the Theory of Computing. pp. 1-9.  1973.
• J.A. Storer.  NP-Completeness Results Concerning Data Compression.  Princeton University Dep. of Engineering, Computer Science Laboratory.  Tech. Report 234.  1977.
• Thomas G. Szymanski.  Assembling Code for Machines with Span-Dependent Instructions. Communications of the ACM. Vol 21, No. 3. 1978.
• D. Tsichritzis. The Equivalence Problem of Simple Programs.  Journal of the ACM. Vol 17, No. 4. pp729-738. 1970.
• J.D. Ullman.  NP-Complete Scheduling Problems.  Journal of Computer and System Sciences 10, pp. 384-393.  1975.
• L.G. Valiant. The Complexity of Computing the Permanent.  Theoretical Computer Science 8, pp. 189-201.  1979.
• Robert A. Wagner.  On the Complexity of the Extended String-To-String Correction Problem. Proceedings of the seventh annual ACM symposium on Theory of computing (STOC 75).  pp. 218-223. 1975.
• Karl Winklmann.  On the Complexity of Some Problems Concerning the Use of Procedures. I.  Acta Informatica 18, 299-318. 1982.
• Mihalis Yannakakis.  Node-and Edge-Deletion NP-Complete Problems.  STOC ’78, pages 253-284. 1978.
• Mihalis Yannakakis.  Edge-Deletion Problems.  SIAM Journal on Computing, Vol 10, No 2. Pages 297-309. 1981.
• M Yannakakis and F Gavril. Edge Dominating Sets in Graphs.  SIAM Journal on Applied Mathematics, Vol 38, No 3.  June 1980.