David S. Johnson - Publications

Last Updated: 20 March 2006

For a list of papers downloadable in electronic format, click here.

Books:

  1. Computers and Intractability: A Guide to the Theory of NP-Completeness, M. R. Garey and D. S. Johnson, W. H. Freeman, 1979.
  2. Discrete Algorithms and Complexity: Proceedings of the Japan-US Joint Seminar, June 4-6, 1986, Kyoto, Japan, D. S. Johnson, T. Nishizeki, A. Nozaki and H. S. Wilf (Editors), Academic Press, New York, 1987.
  3. STOC/FOCS Bibliography, D. S. Johnson (Editor), ACM Press, 1991.
  4. Network Flows and Matching: Proceedings of the 1st DIMACS Implementation Challenge, D. S. Johnson and C. C. McGeoch (Editors), American Mathematical Society, 1993.
  5. Cliques, Coloring, and Satisfiability: Proceedings of the 2nd DIMACS Implementation Challenge, D. S. Johnson and M. A Trick (Editors), American Mathematical Society, 1996.
  6. Data Structures, Near Neighbor Searches, and Methodology: Proceedings of the Fifth and Sixth DIMACS Implementation Challenges, M. Goldwasser, D. S. Johnson, and C. C. McGeoch (Editors), American Mathematical Society, Providence, 2002.

Web Reports:

  1. Challenges for Theoretical Computer Science: DRAFT (June 2000), D. S. Johnson (Editor), http://www.research.att.com/~dsj/nsflist.html.
  2. 8th DIMACS Implementation Challenge: The Traveling Salesman Problem, D. S. Johnson (Editor and Maintainer), http://www.research.att.com/~dsj/chtsp/index.html

NP-Completeness Columns:

  1. The Twelve Open Problems From [G&J]: Updates, J. Algorithms, 2:4 (1981), 393-405.
  2. Embedding Problems, J. Algorithms, 3:1 (1982), 89-99.
  3. Partitioning, Covering, and Packing Problems, J. Algorithms, 3:2 (1982), 182-195.
  4. Oracles, Bin Packing, and and Ordering Problems, J. Algorithms, 3:3 (1982), 288-300.
  5. Routing Problems, J. Algorithms, 3:4 (1982), 381-395.
  6. Knapsacks, Linear Programs, and a Gamut of Problems, J. Algorithms, 4:1 (1983), 87-100.
  7. Parallel Processing, J. Algorithms, 4:2 (1983), pp. 189-203.
  8. Concurrent Processing, J. Algorithms, 4:3 (1983), pp. 286-300.
  9. Fun and Games, J. Algorithms, 4:4 (1983), pp. 397-411.
  10. Updates, Updates, Updates, J. Algorithms, 5:1 (1984), pp. 147-160.
  11. Solving NP-Hard Problems Quickly (On Average), J. Algorithms, 5:2 (1984), pp. 284-299.
  12. Randomized Algorithms and Complexity Classes, J. Algorithms, 5:3 (1984), pp. 433-447.
  13. Communicating Processes, J. Algorithms, 5:4 (1984), pp. 595-609.
  14. Network Design, J. Algorithms, 6:1 (1985), pp. 145-159.
  15. Uniqueness, J. Algorithms, 6:2 (1985), pp. 291-305.
  16. Graph Restrictions and Their Effect, J. Algorithms, 6:3 (1985), pp. 434-451.
  17. Computing with One Hand Tied behind Your Back, J. Algorithms, 7:2 (1986), pp. 289-305.
  18. Computing in the Math Department, Part I, J. Algorithms, 7:4 (1986), pp. 584-601.
  19. The Many Faces of Polynomial Time, J. Algorithms, 8:2 (1987), pp. 285-303.
  20. Announcements, Updates, and Greatest Hits, J. Algorithms, 8:3 (1987), pp. 438-448.
  21. Interactive Proof Systems for Fun and Profit, J. Algorithms, 9:3 (1988), pp. 426-444.
  22. The Story So Far, J. Algorithms, 11:1 (1990), pp. 144-151.
  23. The Tale of the Second Prover, J. Algorithms, 13:3 (1992), pp. 502-524.
  24. Open Problems Revisited, ACM Trans. Algorithms, 1:1 (2005), pp. 160-176.
  25. The Many Limits of Approximation, ACM Trans. Algorithms, 2:3 (2006), pp. 473-489.
  26. Finding Needles in Haystacks, ACM Trans. Algorithms, 3:2 (2007) Article 24, 21 pages.

Technical Papers by Topic:

Theory of NP-Completeness:

  1. Strong NP-Completeness Results: Motivation, Examples, and Implications, M. R. Garey and D. S. Johnson, J. Assoc. Comp. Mach., 25 (1978), 499-508.
  2. How Easy is Local Search?, D. S. Johnson, C. H. Papadimitriou and M. Yannakakis, Journal of Computer and System Sciences, 37:1 (1988), 79-100. [Preliminary version: Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science (1985), 39-42.]
  3. A Catalogue of Complexity Classes, D. S. Johnson, The Handbook of Theor. Comp. Sci., J. Van Leeuwen (editor), Elsevier, 1990, 67-161.

Experimental Methodology:

  1. A Theoretician's Guide to the Experimental Analysis of Algorithms, D. S. Johnson. Data Structures, Near Neighbor Searches, and Methodology: Proceedings of the Fifth and Sixth DIMACS Implementation Challenges, M. Goldwasser, D. S. Johnson, and C. C. McGeoch, Editors, American Mathematical Society, Providence, 2002, 215-250.

Internet Research:

  1. Efficient and robust streaming provisioning in VPNs, Z. M. Mao, D. Johnson, O. Spatscheck, J. E. van der Merwe, and J. Wang, in Proceedings WWW 2003, pp. 118-127.
  2. Scalable and accurate identification of AS-level forwarding paths, Z. M. Mao, D. Johnson, J. Rexford, J. Wang, and R. Katz, in Proceedings INFOCOM 2004.
  3. Compressing rectilinear pictures and minimizing access control lists, D. L. Applegate, G. Calinescu, D. S. Johnson, H. Karloff, K. Ligett, J. Wang, Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms 2007, 1066-1075.

Approximation Algorithms:

  1. Approximation Algorithms for Combinatorial Problems, D. S. Johnson, Journal of Computer and System Sciences, 9 (1974), 256-278. [Preliminary version: Proc. of the 5th Ann. ACM Symp. on Theory of Computing (1973), 38-49.]
  2. Approximation Algorithms for Combinatorial Problems: An Annotated Bibliography, M. R. Garey and D. S. Johnson, Algorithms and Complexity: New Directions and Recent Results, J. F. Traub (editor), Academic Press, 1976, 41-52.

Bin Packing:

  1. Fast Algorithms for Bin Packing, D. S. Johnson, Journal of Computer and System Sciences, 8 (1974), 272-314. [Preliminary version: Fast Allocation Algorithms, Proc. 13th Ann. IEEE Symp. on Switching and Automata Theory (1972), 144-154.]
  2. Worst Case Performance Bounds for Simple One-Dimensional Packing Algorithms, D. S. Johnson, M. R. Garey, R. L. Graham, A. Demers and J. D. Ullman, SIAM J. Computing, 3 (1974), 299-325.
  3. Resource Constrained Scheduling as Generalized Bin Packing, M. R. Garey, R. L. Graham, D. S. Johnson and A. Yao, J. Comb. Theory A, 21 (1976), 257-298.
  4. An Application of Bin Packing to Multiprocessor Scheduling, E. G. Coffman, M. R. Garey and D. S. Johnson, SIAM J. Computing, 7 (1978), 1-17.
  5. On a Number Theoretic Bin Packing Conjecture, M. R. Garey, R. L. Graham and D. S. Johnson, Proc. 5th Hungarian Combinatorics Colloquium, 1978, 377-399.
  6. Performance Bounds for Level-Oriented Two Dimensional Packing Algorithms, E. G. Coffman, M. R. Garey, D. S. Johnson and R. E. Tarjan, SIAM J. Computing, 9 (1980), 808-826.
  7. Approximation Algorithms For Bin Packing Problems: A Survey, M. R. Garey and D. S. Johnson, Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini (editors), Springer-Verlag, 1981, 147-172.
  8. On Packing Two-Dimensional Bins, F. R. K. Chung, M. R. Garey and D. S. Johnson, SIAM J. Algebraic and Discrete Methods, 3 (1982), 66-76.
  9. Dynamic Bin Packing, E. G. Coffman, M. R. Garey and D. S. Johnson, SIAM J. Computing, 12:2 (1983), 227-258.
  10. An Experimental Study of Bin Packing, J. L. Bentley, D. S. Johnson, F. T. Leighton and C. C. McGeoch, Proc. 21st Ann. Allerton Conf. on Communication, Control, and Computing, 1983, 51-60.
  11. Approximation Algorithms for Bin-Packing - An Updated Survey, E. G. Coffman, M. R. Garey and D. S. Johnson, Algorithm Design for Computer System Design, G. Ausiello, M. Lucertini and P. Serafini (editors), Springer-Verlag, 1984, 49-106.
  12. Some Unexpected Behavior Results for Bin-Packing, J. L. Bentley, D. S. Johnson, F. T. Leighton, C. C. McGeoch and L. A. McGeoch, Proc. 16th Ann. ACM Symp. on Theory of Computing, 1984, 279-288. [Journal version of FFD results is still in preparation but should be available soon, see 29 below.]
  13. On a Dual Version of the One-Dimensional Bin Packing Problem, S. F. Assmann, D. S. Johnson, D. J. Kleitman and J. Y.-T. Leung, J. Algorithms, 5:4 (1984), 502-525.
  14. A 71/60 Theorem for Bin Packing, M. R. Garey and D. S. Johnson, J. Complexity, 1 (1985), 65-106.
  15. Bin Packing with Divisible Item Sizes, E. G. Coffman, Jr., M. R. Garey and D. S. Johnson, J. Complexity, 3 (1987), 406-428.
  16. Bounded Space On-Line Bin Packing: Best is Better than First, J. Csirik and D. S. Johnson, Algorithmica 31:2 (2001), 115-138. Preliminary version appeared in Proc. 2nd Ann. ACM-SIAM Symp. on Discrete Algorithms, 1991, 309-319.
  17. Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study, E. G. Coffman, Jr., C. A. Courcoubetis, M. R. Garey, D. S. Johnson, L. A. McGeoch, P. W. Shor, R. R. Weber and M. Yannakakis, Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991, 230-240. [Journal versions: See 21,22,25,30 below.]
  18. Markov Chains, Computer Proofs, and Average-Case Analysis of Best Fit Bin Packing, E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and R. R. Weber, Proc. 25th Ann. ACM Symp. on Theory of Computing, 1993, 412-421.
  19. Probabilistic Analysis of Packing and Related Partitioning Problems, E. G. Coffman, Jr., D. S. Johnson, G. S. Lueker and P. W. Shor, Statistical Science, 8:1 (1993), 40-47.
  20. Approximation Algorithms for Bin Packing: A Survey, E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson, Approximation Algorithms for NP-Hard Problems, D. Hochbaum (editor), PWS Publishing, Boston (1997), 46-93.
  21. Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings, E. G. Coffman, Jr., C. A. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis, SIAM J. Discrete Math. 13 (2000), 384-402.
  22. Bin Packing with Discrete Item Sizes, Part II: Tight Bounds on First Fit, E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and R. R. Weber, Random Structures and Algorithms 10 (1997), 69-101.
  23. A Self-Organizing Bin Packing Heuristic, J. Csirik, D. S. Johnson, C. Kenyon, P. W. Shor and R. R. Weber, in Algorithm Engineering and Experimentation, M. T. Goodrich and C. C. McGeoch (Eds.), Springer Lecture Notes in Computer Science 1619 (1999), 246-265.
  24. Better Approximation Algorithms for Bin Covering, J. Csirik, D. S. Johnson, and C. Kenyon, in Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (2001), 557-566.
  25. Perfect Packing Theorems and the Average Case Behavior of Optimal and Online Bin Packing, E. G. Coffman, Jr., C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, and M. Yannakakis, SIAM Review 44 (2002), 95-108. [Updated version of 21 above.]
  26. The Cutting-Stock Approach to Bin Packing: Theory and Experiments, D. L. Applegate, L. S. Buriol, B. L. Dillard, D. S. Johnson, and P. W. Shor. in Proceedings of the Fifth Workshop on Algorithm Engineering and Experimentation, R.E. Ladner (Editor), SIAM, 2003, pp 1-15.
  27. On the Sum-of-Squares Algorithm for Bin Packing, J. Csirik, D. S. Johnson, C. Kenyon, J. B. Orlin, P. W. Shor and R. R. Weber, J.ACM 53, (2006), 1-65. [Preliminary version: Proc. 32nd Annual ACM Symp. on Theory of Computing (2000), 208-217.]
  28. On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing, J. Csirik, D. S. Johnson, and C. Kenyon, arXiv.org E-print arXiv:cs.DS/0509031 at http://arxiv.org/archive/cs.
    ---------
  29. The Expected Behavior of FFD, BFD, and Optimal Bin Packing under U(0,a] Distributions, E. G. Coffman, Jr., D. S. Johnson, F. T. Leighton, P. W. Shor and R. R. Weber (in preparation).
  30. Bin Packing with Discrete Item Sizes, Part III: Average Case Behavior of FFD and BFD, E. G. Coffman, Jr., D. S. Johnson, L. A. McGeoch, P. W. Shor and R. R. Weber (in preparation).

The Traveling Salesman Problem:

  1. The Planar Hamiltonian Circuit Problem is NP-Complete, M. R. Garey, D. S. Johnson and R. E. Tarjan, SIAM J. Computing, 5 (1976), pp. 704-714.
  2. Some NP-Complete Geometric Problems, M. R. Garey, R. L. Graham and D. S. Johnson, Proc. 8th Annual ACM Symp. on Theory of Computing, 1976, pp. 10-22.
  3. Computational Complexity, D. S. Johnson and C. H. Papadimitriou, The Traveling Salesman Problem, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys (editors), John-Wiley and Sons, Ltd., 1985, pp. 37-85.
  4. Performance Guarantees for Heuristics, D. S. Johnson and C. H. Papadimitriou, The Traveling Salesman Problem, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys (editors), John-Wiley and Sons, Ltd., 1985, pp. 145-180.
  5. Local Optimization and the Traveling Salesman Problem, D. S. Johnson, Proc. 17th Colloq. on Automata, Lang. and Prog., 1990, pp. 446-461.
  6. Data Structures for Traveling Salesmen, M. L. Fredman, D. S. Johnson, L. A. McGeoch and G. Ostheimer, J. Algorithms, 18:3 (1995), pp. 432-479. [Preliminary version: Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms (1993), 145-154.]
  7. Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound, D. S. Johnson, L. A. McGeoch, and E. E. Rothberg, Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1996, pp. 341-350.
  8. The Traveling Salesman Problem: A Case Study in Local Optimization, D. S. Johnson and L. A. McGeoch, Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra (editors), John-Wiley and Sons, Ltd., 1997, pp. 215-310.
  9. Near-optimal Intraprocedural Branch Alignment, C. Young, D. S. Johnson, D. R. Karger, and M. D. Smith, Proceedings 1997 Symp. on Programming Languages, Design, and Implementation, 1997, 183-193.
  10. The Geometric Maximum Traveling Salesman Problem, A. Barvinok, S. Fekete, D. S. Johnson, A. Tamir, G. J. Woeginger, and R. Woodroofe. JACM 50:5 (2003), 641-664. [Journal version of The Maximum Traveling Salesman Problem under Polyhedral Norms,," A. Barvinok, G. J. Woeginger, D. S. Johnson, and R. Woodroofe, in Integer Programming and Combinatorial Optimization, R. E. Bixby, E. A. Boyd, and R. Z. Rios-Mercado (Eds.), Springer Lecture Notes in Computer Science 1412 (1998), 195-201, combined with Fekete's 1999 SODA paper and faster algorithms.]
  11. The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, J. Cirasella, D. S. Johnson, L. A. McGeoch, and W. Zhang, ALENEX 2001 Proceedings, Springer Lecture Notes in Computer Science 2153, A. L. Buchsbaum and J. Snoeyink (eds.), 32-59.
  12. Experimental Analysis of Heuristics for the STSP, D. S. Johnson and L. A. McGeoch, in The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Editors, Kluwer Academic Publishers, Dordrecht, 2002, 369-443.
  13. Experimental Analysis of Heuristics for the ATSP, D. S. Johnson, G. Gutin, L. A. McGeoch, A. Yeo, W. Zhang, and A. Zverovich, in The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Editors, Kluwer Academic Publishers, Dordrecht, 2002, 445-487.
  14. Compressing Large Boolean Matrices using Reordering Techniques, D. S. Johnson, S. Krishnan, J. Chhugani, S. Kumar, and S. Venkatasubramanian in Proc. 30th Int. Conf. on Very Large Databases (VLDB), 2004, 13-23.
  15. vLOD: High Fidelity Walkthroughs of Large Virtual Environments, J. Chhugani, B. Purnomo, S. Krishnan, J. Cohen, S. Venkatasubramanian, D. Johnson, and S. Kumar, IEEE Trans. Visualization and Computer Graphics , 11 (2005), 35-47.

Scheduling:

  1. Complexity Results for Multiprocessor Scheduling Under Resource Constraints, M. R. Garey and D. S. Johnson, SIAM J. Computing, 4 (1975), 397-411. [Preliminary version: Proc. 8th Ann. Princeton Conference on Information Sciences and Systems (1974), 168-172.]
  2. Scheduling Tasks with Non-uniform Deadlines on Two Processors, M. R. Garey and D. S. Johnson, J. Assoc. Comp. Mach., 23 (1976), 461-467.
  3. The Complexity of Flowshop and Jobshop Scheduling, M. R. Garey, D. S. Johnson and R. Sethi, Math. of Oper. Research, 2:2 (May 1976), 117-129.
  4. Two-Processor Scheduling with Start-Times and Deadlines, M. R. Garey and D. S. Johnson, SIAM J. Computing, 6 (1977), 416-426.
  5. Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness, P. Brucker, M. R. Garey and D. S. Johnson, Math. of Oper. Research, 2 (1977), 275-284.
  6. Performance Guarantees for Scheduling Algorithms, M. R. Garey, R. L. Graham and D. S. Johnson, Operations Research, 26:1 (1978), 3-21.
  7. Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines, M. R. Garey, D. S. Johnson, B. B. Simons and R. E. Tarjan, SIAM J. Computing, 1981, 256-269.
  8. Scheduling Opposing Forests, M. R. Garey, D. S. Johnson, R. E. Tarjan and M. Yannakakis, SIAM J. Algebraic and Discrete Methods, 4:1 (1983), 72-93.
  9. Scheduling File Transfers, E. G. Coffman, Jr., M. R. Garey, D. S. Johnson and A. S. LaPaugh, SIAM J. Comput., 14:3 (1985), 744-780. [Preliminary version: Scheduling File Transfers in a Distributed Network, Proc. 2nd Ann. ACM Symp. on Principles of Distributed Computing (1983), 254-266.]

Graph Coloring and Partitioning:

  1. Worst Case Behavior of Graph Coloring Algorithms, D. S. Johnson, Proc. 5th Southeastern Conf. on Comb., Graph Theory and Computing, 1974, 513-527.
  2. The Complexity of Near Optimal Graph Coloring, M. R. Garey and D. S. Johnson, J. Assoc. Comp. Mach., 23 (1976), 43-49.
  3. An Application of Graph Coloring To Printed Circuit Testing, M. R. Garey, D. S. Johnson and H. C. So, IEEE Trans. on Circuits and Systems, CAS-23 (1976), 591-599. [Preliminary version: Proc. 16th Ann. Symp. on Foundations of Computer Science (1975), 178-183.]
  4. Two Results Concerning Multicoloring, V. Chvatal, M. R. Garey and D. S. Johnson, Ann. Disc. Math., 2 (1978), 151-154.
  5. A Note on Bisecting Minimum Spanning Trees, W. M. Boyce, M. R. Garey and D. S. Johnson, Networks, 8 (1978), 187-192.
  6. On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees, D. S. Johnson and K. A. Niemi, Math. of Oper. Research, 8:1 (1983), 1-14.
  7. The Complexity of Coloring Circular Arcs and Chords, M. R. Garey, D. S. Johnson, G. L. Miller and C. H. Papadimitriou, SIAM J. Algebraic and Discrete Methods, 1 (1980), 216-227.
  8. Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning, D. S. Johnson, C. R. Aragon, L. A. McGeoch and C. Shevon, Operations Research, 37:6 (1989), 865-892.
  9. Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning, D. S. Johnson, C. R. Aragon, L. A. McGeoch and C. Schevon, Operations Research, 39:3 (1991), 378-406.
  10. The Complexity of Multiterminal Cuts, E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour and M. Yannakakis, SIAM J. Computing, 23 (1994), pp. 864-894. [Preliminary version: The Complexity of Multiway Cuts, Proc. 24th Ann. ACM Symp. on Theory of Computing (1992), 241-251.]
  11. Simulation Results of the Capacity of Cellular Systems, Z. J. Haas, J. H. Winters, and D. S. Johnson, IEEE Trans. Vehicular Technology 46:4 (1997), pp. 805-817. [Combined journal version of two proceedings papers: Simulation Results of Cellular Capacity Bounds, Z. J. Haas, J. H. Winters, and D. S. Johnson, Proc. Personal Indoor Mobile Radio Conference, (1994), 1114-1120, and Additional Results on the Capacity Bounds in Cellular Systems, Z. J. Haas, J. H. Winters, and D. S. Johnson, Proc. GLOBECOM, (1994), 1652-1658.]

Computational Geometry and Network Design:

  1. The Complexity of Computing Steiner Minimal Trees, M. R. Garey, R. L. Graham and D. S. Johnson, SIAM J. Appl. Math., 32 (1977), pp. 835-859.
  2. The Rectilinear Steiner Tree Problem is NP-Complete, M. R. Garey and D. S. Johnson, SIAM J. Appl. Math., 32 (1977), pp. 826-834.
  3. The Densest Hemisphere Problem, D. S. Johnson and F. P. Preparata, Theoretical Comp. Sci., 6 (1978), 93-107.
  4. Triangulating a Simple Polygon, M. R. Garey, D. S. Johnson, F. P. Preparata and R. E. Tarjan, Information Processing Letters, 7 (1978), pp. 175-179.
  5. Minimizing Channel Density by Lateral Shifting of Components, D. S. Johnson, A. S. LaPaugh and R. Y. Pinter, Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1994, 122-131.
  6. The Prize Collecting Steiner Tree Problem: Theory and Practice, D. S. Johnson, M. Minkoff, and S. Phillips, Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, 2000, 760-769.

Database Theory:

  1. Optimizing Conjunctive Queries that Contain Untyped Variables, D. S. Johnson and A. Klug, SIAM J. Computing, 12:4 (1983), pp. 616-640. [Preliminary version: Optimizing Conjunctive Queries When Attribute Domains are not Disjoint, Proc. 22nd Ann. Symp. on Foundations of Computer Science (1981), 203-211.]
  2. Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies, D. S. Johnson and A. Klug, Journal of Computer and Systems Sciences, 28 (1984), pp. 167-189. [Preliminary version: Proc. 1st Ann. ACM Symp. on Principles of Database Systems (1982), 164-169.]

Miscellaneous NP-Completeness Results (and Algorithms):

  1. Some Simplified NP-Complete Graph Problems, M. R. Garey, D. S. Johnson and L. Stockmeyer, Theoretical Comp. Sci., 1 (1976), 237-267. [Preliminary version: Some Simplified NP-complete Problems, Proc. 6th Ann. ACM Symp. on Theory of Computing (1974), 47-63.]
  2. A Note on "A Note on 'Some Simplified NP-Complete Graph Problems'", M. R. Garey and D. S. Johnson, SIGACT News, 9:4 (1978), page 17.
  3. The Complexity of Checkers on an NxN Board: Preliminary Report, A. S. Fraenkel, M. R. Garey, D. S. Johnson, T. Schaefer and Y. Yesha, Proc. 19th Annual Symposium on Foundations of Computer Science, 1978, 55-64.
  4. Complexity Results for Bandwidth Minimization, M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth, SIAM J. Appl. Math., 34:3 (1978), 477-495.
  5. The Complexity of the Network Design Problem, D. S. Johnson, J. K. Lenstra and A. H. G. Rinnooy Kan, Networks, 8 (1978), 279-285.
  6. The Complexity of the Generalized Lloyd-Max Problem, M. R. Garey, D. S. Johnson and H. S. Witsenhausen, IEEE Trans. on Information Theory, IT-28 (1982), 255-256.
  7. Crossing Number is NP-Complete, M. R. Garey and D. S. Johnson, SIAM J. Algebraic and Discrete Methods, 4:3 (1983), 312-316.
  8. The Computational Complexity of Inferring Rooted Phylogenies by Parsimony, W. H. E. Day, D. S. Johnson and D. Sankoff, Math. Biosciences, 81 (1986), 33-42.
  9. Hypergraph Planarity and the Complexity of Drawing Venn Diagrams, D. S. Johnson and H. O. Pollack, J. Graph Theory, 11:3 (1987), 309-325. [Preliminary version: Proc. Symp. on Theory of Algorithms (Pecs, Hungary) (1984), 241-249.]
  10. The Complexity of Searching a Graph, N. S. Megiddo, S. L. Hakimi, M. R Garey, D. S. Johnson and C. H. Papadimitriou, J. Assoc. Comp. Mach., 35:1 (1988), 18-44. [Preliminary version: Proc. 22nd Ann. Symp. on Foundations of Computer Science (1981), 376-385.]
  11. On Generating all Maximal Independent Sets, D. S. Johnson, C. H. Papadimitriou and M. Yannakakis, Information Processing Letters, 27:3 (1988), 119-123.
  12. Generalized Planar Matching, F. Berman, D. S. Johnson, T. Leighton, P. W. Shor and L. Snyder, J. Algorithms, 11:2 (1990), 153-184.
  13. Unit Disk Graphs, C. J. Colbourn and D. S. Johnson, Discrete Math., 86 (1990), 165-177.

Miscellaneous Other Papers:

  1. On Property $B_r$, D. S. Johnson, J. Comb. Theory B, 20 (1976), 64-66.
  2. Algorithms for a Set Partitioning Problem Arising in the Design of Multi-Purpose Units, M. R. Garey, F. K. Hwang and D. S. Johnson, IEEE Trans. on Computers, C-26 (1977), 321-328.
  3. What are the Least Tractable Instances of Max Independent Set?, D. S. Johnson and M. Szegedy, in Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1999, S927-S928.
  4. The Genealogy of Theoretical Computer Science, D. S. Johnson, SIGACT News, 16:2 (1984), 36-49.

Letters to the Editor:

  1. More Approaches to the Travelling Salesman Guide, D. S. Johnson, Nature, 330 (1987), page 525.
  2. Slow Ant, D. S. Johnson, New Scientist, 46 (27 August 1994), page 525.


Go to David Johnson's Home Page