Edit Profile (opens in new tab) Johnson, David Stifler Co-Author Distance Author ID: johnson.david-stifler Published as: Johnson, David S.; Johnson, D. S.; Johnson, David; Johnson, David Stifler more...less Homepage: http://davidsjohnson.net/ External Links: MGP · Wikidata · dblp · GND · IdRef Documents Indexed: 119 Publications since 1973, including 2 Books 8 Contributions as Editor · 2 Further Contributions Biographic References: 2 Publications Co-Authors: 95 Co-Authors with 92 Joint Publications 4,530 Co-Co-Authors all top 5 Co-Authors 35 single-authored 42 Garey, Michael Randolph 10 Coffman, Edward Grady jun. 9 McGeoch, Lyle A. 8 Graham, Ronald Lewis 8 Shor, Peter Williston 7 Papadimitriou, Christos Harilaos 5 Csirik, János A. 5 Tarjan, Robert Endre 4 Weber, Richard Robert 4 Yannakakis, Mihalis 3 Garay, Juan A. 3 Karloff, Howard J. 3 Kenyon, Claire M. 3 Kiayias, Aggelos 3 Yung, Moti 2 Aragon, Cecilia R. 2 Barvinok, Alexander I. 2 Breslau, Lee 2 Courcoubetis, Costas A. 2 Diakonikolas, Ilias 2 Duffield, Nick G. 2 Fredman, Michael L. 2 Gu, Yu 2 LaPaugh, Andrea S. 2 Lenstra, Jan Karel 2 McGeoch, Catherine C. 2 Orlin, James B. 2 Pollak, Henry O. 2 Preparata, Franco P. 2 Resende, Mauricio G. C. 2 Rinnooy Kan, Alexander Hendrik George 2 Schevon, Catherine A. 2 Sen, Subhabrata 2 Trick, Michael A. 2 Woeginger, Gerhard 2 Zhang, Weixiong 1 Applegate, David A. 1 Assmann, Susan F. 1 Ausiello, Giorgio 1 Babai, László 1 Berman, Fran 1 Bermond, Jean-Claude 1 Boyce, William M. 1 Brouwer, Andries Evert 1 Brucker, Peter J. 1 Calinescu, Gruia 1 Chung, Fan 1 Chvátal, Václav 1 Cirasella, Jill 1 Clark, Brent N. 1 Colbourn, Charles J. 1 Dahlhaus, Elias 1 D’Atri, Alessandro 1 Day, William H. E. 1 Daykin, D. K. 1 Demers, Alan J. 1 Demetrescu, Camil 1 Deza, Michel Marie 1 Epstein, Leah 1 Fekete, Sándor P. 1 Fiedler, Miroslav 1 Frankl, Péter 1 Gelles, Ran 1 Geréb, Mihály 1 Giulianelli, S. 1 Goldberg, Andrew V. 1 Goldwasser, Michael H. 1 Grünbaum, Branko 1 Gutin, Gregory Z. 1 Gutman, Ivan M. 1 Gyárfás, András 1 Häggkvist, Roland 1 Hajiaghayi, Mohammad Taghi 1 Hajiaghayi, Mohammad Taghii 1 Hakimi, Seifollah Louis 1 Harborth, Heiko 1 Hilton, Anthony J. W. 1 Hoede, Cornelis 1 Hwang, Frank Kwangming 1 Katona, Gyula O. H. 1 Kleitman, Daniel J. 1 Knuth, Donald Ervin 1 Kurepa, Đuro R. 1 Lawler, Eugene L. 1 Leighton, Tom 1 Leung, Joseph Y.-T. 1 Levin, Asaf 1 Ligett, Katrina 1 Lovász, László 1 Lucertini, Mario 1 Lueker, George S. 1 Maffioli, Francesco 1 Megiddo, Nimrod 1 Miller, Gary Lee 1 Minkoff, Maria 1 Nešetřil, Jaroslav 1 Niemi, K. A. 1 Nishizeki, Takao 1 Nozaki, Akihiro 1 Phillips, Steven J. ...and 34 more Co-Authors all top 5 Serials 26 Journal of Algorithms 12 SIAM Journal on Computing 4 Journal of the Association for Computing Machinery 4 Journal of Computer and System Sciences 4 Operations Research 4 SIAM Journal on Algebraic and Discrete Methods 4 DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 3 Mathematics of Operations Research 3 Theoretical Computer Science 3 SIAM Journal on Applied Mathematics 3 ACM Transactions on Algorithms 2 Information Processing Letters 2 Networks 2 Journal of the ACM 1 Discrete Mathematics 1 IEEE Transactions on Information Theory 1 Mathematical Biosciences 1 IEEE Transactions on Circuits and Systems 1 IEEE Transactions on Computers 1 Journal of Combinatorial Theory. Series A 1 Journal of Combinatorial Theory. Series B 1 Journal of Graph Theory 1 Journal of Complexity 1 Algorithmica 1 SIAM Journal on Discrete Mathematics 1 Random Structures & Algorithms 1 SIAM Review 1 Documenta Mathematica 1 Journal of Combinatorial Optimization 1 CISM International Centre for Mechanical Sciences. Courses and Lectures 1 Perspectives in Computing all top 5 Fields 102 Computer science (68-XX) 50 Operations research, mathematical programming (90-XX) 37 Combinatorics (05-XX) 20 General and overarching topics; collections (00-XX) 12 Information and communication theory, circuits (94-XX) 6 Numerical analysis (65-XX) 4 Mathematical logic and foundations (03-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Number theory (11-XX) 1 Group theory and generalizations (20-XX) 1 Geometry (51-XX) 1 Probability theory and stochastic processes (60-XX) 1 Biology and other natural sciences (92-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 122 Publications have been cited 16,555 times in 14,101 Documents Cited by ▼ Year ▼ Computers and intractability. A guide to the theory of NP-completeness. Zbl 0411.68039 Garey, Michael R.; Johnson, David S. 9,485 1979 Some simplified NP-complete graph problems. Zbl 0338.05120 Garey, M. R.; Johnson, D. S.; Stockmeyer, L. 673 1976 Approximation algorithms for combinatorial problems. Zbl 0296.65036 Johnson, David S. 410 1974 The complexity of flow shop and jobshop scheduling. Zbl 0396.90041 Garey, M. R.; Johnson, D. S.; Sethi, Ravi 389 1976 The rectilinear Steiner tree problem is NP-complete. Zbl 0396.05009 Garey, M. R.; Johnson, D. S. 260 1977 Unit disk graphs. Zbl 0739.05079 Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. 239 1990 “Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035 Garey, M. R.; Johnson, D. S. 233 1978 The complexity of multiterminal cuts. Zbl 0809.68075 Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. 224 1994 On generating all maximal independent sets. Zbl 0654.68086 Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. 207 1988 Optimization by simulated annealing: An experimental evaluation. I: Graph partitioning. Zbl 0698.90065 Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 202 1989 Worst-case performance bounds for simple one-dimensional packing algorithms. Zbl 0297.68028 Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L. 199 1975 The planar Hamiltonian circuit problem is NP-complete. Zbl 0346.05110 Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre 179 1976 Crossing number is NP-complete. Zbl 0536.05016 Garey, M. R.; Johnson, D. S. 168 1983 How easy is local search? Zbl 0655.68074 Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 166 1988 A catalog of complexity classes. Zbl 0900.68246 Johnson, David S. 148 1990 Optimization by simulated annealing: An experimental evaluation. II: Graph coloring and number partitioning. Zbl 0739.90055 Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 133 1991 An application of bin-packing to multiprocessor scheduling. Zbl 0374.68032 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 129 1978 Fast algorithms for bin packing. Zbl 0284.68023 Johnson, David S. 126 1974 The complexity of computing Steiner minimal trees. Zbl 0399.05023 Garey, M. R.; Graham, R. L.; Johnson, D. S. 125 1977 The complexity of searching a graph. Zbl 0637.68081 Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. 123 1988 The traveling salesman problem: A case study. Zbl 0947.90612 Johnson, David S.; McGeoch, Lyle A. 122 1997 Approximation algorithms for bin-packing - an updated survey. Zbl 0558.68062 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 117 1984 The NP-completeness column: An ongoing guide. XVI. Zbl 0608.68032 Johnson, David S. 112 1985 Two-processor scheduling with start-times and deadlines. Zbl 0369.90053 Garey, M. R.; Johnson, D. S. 110 1977 Performance bounds for level-oriented two-dimensional packing algorithms. Zbl 0447.68079 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Tarjan, R. E. 109 1980 Complexity results for bandwidth minimization. Zbl 0385.05048 Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E. 109 1978 The complexity of coloring circular arcs and chords. Zbl 0499.05058 Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. 108 1980 Complexity results for multiprocessor scheduling under resource constraints. Zbl 0365.90076 Garey, M. R.; Johnson, D. S. 93 1975 The complexity of the network design problem. Zbl 0395.94048 Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G. 86 1978 Introduction to the second DIMACS challenge: Cliques, coloring, and satisfiability. Zbl 0875.68678 Johnson, David S.; Trick, Michael A. 86 1996 The prize collecting Steiner tree problem: Theory and practice. Zbl 0956.68112 Johnson, David S.; Minkoff, Maria; Phillips, Steven 76 2000 Resource constrained scheduling as generalized bin packing. Zbl 0384.90053 Garey, M. R.; Graham, R. L.; Johnson, D. S.; Yao, Andrew Chi-Chih 75 1976 The complexity of near-optimal graph coloring. Zbl 0322.05111 Garey, M. R.; Johnson, D. S. 67 1976 Local optimization and the traveling salesman problem. Zbl 0766.90079 Johnson, David S. 62 1990 Some NP-complete geometric problems. Zbl 0377.68036 Garey, M. R.; Graham, R. L.; Johnson, D. S. 60 1976 On knapsacks, partitions, and a new dynamic programming technique for trees. Zbl 0506.90035 Johnson, D. S.; Niemi, K. A. 60 1983 Triangulating a simple polygon. Zbl 0384.68040 Garey, Michael R.; Johnson, David S.; Preparata, Franco P.; Tarjan, Robert E. 59 1978 On packing two-dimensional bins. Zbl 0495.05016 Chung, F. R. K.; Garey, M. R.; Johnson, D. S. 59 1982 On a dual version of the one-dimensional bin packing problem. Zbl 0556.68011 Assmann, S. F.; Johnson, D. S.; Kleitman, D. J.; Leung, J. Y.-T. 57 1984 Experimental analysis of heuristics for the STSP. Zbl 1113.90356 Johnson, David S.; McGeoch, Lyle A. 51 2002 Testing containment of conjunctive queries under functional and inclusion dependencies. Zbl 0563.68081 Johnson, D. S.; Klug, A. 42 1984 Scheduling unit-time tasks with arbitrary release times and deadlines. Zbl 0472.68021 Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E. 40 1981 Scheduling file transfers. Zbl 0604.68039 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Lapaugh, A. S. 38 1985 The densest hemisphere problem. Zbl 0368.68053 Johnson, D. S.; Preparata, F. P. 37 1978 Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Zbl 0845.90123 Johnson, D. S.; McGeoch, L. A.; Rothberg, E. E. 37 1996 Scheduling tasks with nonuniform deadlines on two processors. Zbl 0338.68048 Garey, M. R.; Johnson, D. S. 34 1976 Dynamic bin packing. Zbl 0512.68050 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 30 1983 Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Zbl 0397.90044 Brucker, Peter; Garey, M. R.; Johnson, D. S. 29 1977 An application of graph coloring to printed circuit testing. Zbl 0342.94021 Garey, Michael R.; Johnson, David Stifler; So, Hing C. 28 1976 A theoretician’s guide to the experimental analysis of algorithms. Zbl 1103.68997 Johnson, David S. 26 2002 The NP-completeness column: An ongoing guide. XX. Zbl 0633.68022 Johnson, David S. 25 1987 Experimental analysis of heuristics for the ATSP. Zbl 1113.90355 Johnson, David S.; Gutin, Gregory; McGeoch, Lyle A.; Yeo, Anders; Zhang, Weixiong; Zverovitch, Alexei 25 2002 The NP-completeness column: An ongoing guide. III. Zbl 0494.68049 Johnson, David S. 25 1982 The asymmetric traveling salesman problem: algorithms, instance generators, and tests. Zbl 1010.68848 Cirasella, Jill; Johnson, David S.; McGeoch, Lyle A.; Zhang, Weixiong 23 2001 A 71/60 theorem for bin packing. Zbl 0604.68046 Johnson, David S.; Garey, Michael R. 22 1985 The maximum traveling salesman problem under polyhedral norms. Zbl 0910.90259 Barvinok, Alexander; Johnson, David S.; Woeginger, Gerhard J.; Woodroofe, Russell 22 1998 The NP-completeness column: An ongoing guide. I. Zbl 0494.68047 Johnson, David S. 22 1981 Cliques, coloring, and satisfiability. Second DIMACS implementation challenge. Proceedings of a workshop held at DIMACS, October 11–13, 1993. Zbl 0851.00080 21 1996 Scheduling opposing forests. Zbl 0507.68021 Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M. 21 1983 Better approximation algorithms for bin covering. Zbl 1018.90037 Csirik, Janos; Johnson, David S.; Kenyon, Claire 20 2001 Performance guarantees for heuristics. Zbl 0574.90086 Johnson, D. S.; Papadimitriou, C. H. 20 1985 The computational complexity of inferring rooted phylogenies by parsimony. Zbl 0607.92002 Day, William H. E.; Johnson, David S.; Sankoff, David 20 1986 Hypergraph planarity and the complexity of drawing Venn diagrams. Zbl 0654.05055 Johnson, D. S.; Pollak, H. O. 20 1987 Performance guarantees for scheduling algorithms. Zbl 0371.90068 Garey, M. R.; Graham, R. L.; Johnson, D. S. 19 1978 Generalized planar matching. Zbl 0731.68041 Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry 19 1990 The NP-completeness column: An ongoing guide. XIX. Zbl 0626.68039 Johnson, David S. 18 1987 Data structures for traveling salesmen. Zbl 0829.90132 Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G. 18 1995 The NP-completeness column: An ongoing guide. XI. Zbl 0546.68025 Johnson, David S. 18 1984 The NP-completeness column: An ongoing guide. X. Zbl 0545.68032 Johnson, David S. 18 1984 Computers and intractability. Transl. from the English by E. V. Levner and M. A. Frumkin. (Вычислителъные машины и труднорешаемые задачи.) Zbl 0522.68040 Garey, Michael R.; Johnson, David S. 17 1982 Bounded space on-line bin packing: Best is better than first. Zbl 0980.68141 Csirik, J.; Johnson, D. S. 16 2001 What are the least tractable instances of max independent set? Zbl 0929.68089 Johnson, David S.; Szegedy, Mario 15 1999 Approximation algorithms for combinatorial problems. Zbl 0316.68024 Johnson, David S. 15 1973 The NP-completeness column. Zbl 1442.68065 12 2005 Network flows and matching. 1st DIMACS Implementation Challenge. Zbl 0781.00013 12 1993 The shortest path problem. Ninth DIMACS implementation challenge, Piscataway, NJ, USA, November 13–14, 2006. Proceedings. Zbl 1172.05005 12 2009 The NP-completeness column: an ongoing guide. XIV. Zbl 0562.68032 Johnson, David S. 11 1985 The complexity of the generalized Lloyd-Max problem. Zbl 0476.94009 Garey, M. R.; Johnson, D. S.; Witsenhausen, Hans S. 11 1982 The NP-completeness column: An ongoing guide. II. Zbl 0494.68048 Johnson, David S. 11 1982 The NP-completeness column: An ongoing guide. IV. Zbl 0494.68050 Johnson, David S. 11 1982 Two results concerning multicoloring. Zbl 0374.05025 Chvatal, V.; Garey, M. R.; Johnson, D. S. 10 1978 Approximation algorithms for combinatorial problems: An annotated bibliography. Zbl 0382.05001 Garey, M. R.; Johnson, D. S. 10 1976 The geometric maximum traveling salesman problem. Zbl 1325.90074 Barvinok, Alexander; Fekete, Sándor P.; Johnson, David S.; Tamir, Arie; Woeginger, Gerhard J.; Woodroofe, Russ 9 2003 The NP-completeness column: An ongoing guide. Zbl 0588.68020 Johnson, David S. 9 1985 The NP-completeness column: An ongoing guide. V. Zbl 0502.68007 Johnson, David S. 9 1982 Bin packing with discrete item sizes. I: Perfect packing theorems and the average case behavior of optimal packings. Zbl 0951.68192 Coffman, E. G. jun.; Courcoubetis, C.; Garey, M. R.; Johnson, D. S.; Shor, P. W. 8 2000 The NP-completeness column: an ongoing guide. VII. Zbl 0509.68035 Johnson, David S. 8 1983 Worst case behavior of graph coloring algorithms. Zbl 0308.05109 Johnson, David S. 7 1974 On the sum-of-squares algorithm for bin packing. Zbl 1296.68076 Csirik, Janos; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 7 2000 Markov chains, computer proofs, and average-case analysis of best fit bin packing. Zbl 1310.68271 Coffman, E. G.; Johnson, D. S.; Shor, P. W.; Weber, R. R. 7 1993 Bounded space on-line bin packing: Best is better than first. Zbl 0800.68478 Csirik, J.; Johnson, D. S. 7 1991 The NP-completeness column: an ongoing guide. IX. Zbl 0532.68050 Johnson, David S. 7 1983 On the sum-of-squares algorithm for bin packing. Zbl 1326.68334 Csirik, János; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 7 2006 The NP-completeness column: finding needles in haystacks. Zbl 1445.68103 5 2007 Computational complexity. Zbl 0578.90087 Johnson, D. S.; Papadimitriou, C. H. 5 1985 The NP-completeness column: An ongoing guide. XVII. Zbl 0608.68033 Johnson, David S. 5 1986 Compressing rectilinear pictures and minimizing access control lists. Zbl 1302.68297 Applegate, David A.; Calinescu, Gruia; Johnson, David S.; Karloff, Howard; Ligett, Katrina; Wang, Jia 5 2007 The NP-completeness column: An ongoing guide. XXI. Zbl 0651.68054 Johnson, David S. 5 1988 Optimizing conjunctive queries that contain untyped variables. Zbl 0524.68059 Johnson, D. S.; Klug, A. 5 1983 Resource-based corruptions and the combinatorics of hidden diversity. Zbl 1364.94537 Garay, Juan; Johnson, David; Kiayias, Aggelos; Yung, Moti 4 2013 Near-optimal disjoint-path facility location through set cover by pairs. Zbl 1445.90017 Johnson, David S.; Breslau, Lee; Diakonikolas, Ilias; Duffield, Nick; Gu, Yu; Hajiaghayi, Mohammad Taghii; Karloff, Howard; Resende, Mauricio G. C.; Sen, Subhabrata 1 2020 Min-sum bin packing. Zbl 1421.90125 Epstein, Leah; Johnson, David S.; Levin, Asaf 2 2018 A little honesty goes a long way. The two-tier model for secure multiparty computation. Zbl 1354.94029 Garay, Juan A.; Gelles, Ran; Johnson, David S.; Kiayias, Aggelos; Yung, Moti 1 2015 Resource-based corruptions and the combinatorics of hidden diversity. Zbl 1364.94537 Garay, Juan; Johnson, David; Kiayias, Aggelos; Yung, Moti 4 2013 A brief history of NP-completeness, 1954–2012. Zbl 1260.68007 Johnson, David S. 2 2012 Disjoint-path facility location: theory and practice. Zbl 1429.68185 Breslau, Lee; Diakonikolas, Ilias; Duffield, Nick; Gu, Yu; Hajiaghayi, Mohammad Taghi; Johnson, David S.; Karloff, Howard; Resende, Mauricio G. C.; Sen, Subhabrata 2 2011 The shortest path problem. Ninth DIMACS implementation challenge, Piscataway, NJ, USA, November 13–14, 2006. Proceedings. Zbl 1172.05005 12 2009 The NP-completeness column: finding needles in haystacks. Zbl 1445.68103 5 2007 Compressing rectilinear pictures and minimizing access control lists. Zbl 1302.68297 Applegate, David A.; Calinescu, Gruia; Johnson, David S.; Karloff, Howard; Ligett, Katrina; Wang, Jia 5 2007 On the sum-of-squares algorithm for bin packing. Zbl 1326.68334 Csirik, János; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 7 2006 The NP-completeness column. Zbl 1442.68065 12 2005 The geometric maximum traveling salesman problem. Zbl 1325.90074 Barvinok, Alexander; Fekete, Sándor P.; Johnson, David S.; Tamir, Arie; Woeginger, Gerhard J.; Woodroofe, Russ 9 2003 Experimental analysis of heuristics for the STSP. Zbl 1113.90356 Johnson, David S.; McGeoch, Lyle A. 51 2002 A theoretician’s guide to the experimental analysis of algorithms. Zbl 1103.68997 Johnson, David S. 26 2002 Experimental analysis of heuristics for the ATSP. Zbl 1113.90355 Johnson, David S.; Gutin, Gregory; McGeoch, Lyle A.; Yeo, Anders; Zhang, Weixiong; Zverovitch, Alexei 25 2002 Perfect packing theorems and the average-case behavior of optimal and online bin packing. Zbl 0999.68260 Coffman, E. G. jun.; Courcoubetis, C.; Garey, M. R.; Johnson, D. S.; Shor, P. W. 1 2002 The asymmetric traveling salesman problem: algorithms, instance generators, and tests. Zbl 1010.68848 Cirasella, Jill; Johnson, David S.; McGeoch, Lyle A.; Zhang, Weixiong 23 2001 Better approximation algorithms for bin covering. Zbl 1018.90037 Csirik, Janos; Johnson, David S.; Kenyon, Claire 20 2001 Bounded space on-line bin packing: Best is better than first. Zbl 0980.68141 Csirik, J.; Johnson, D. S. 16 2001 The prize collecting Steiner tree problem: Theory and practice. Zbl 0956.68112 Johnson, David S.; Minkoff, Maria; Phillips, Steven 76 2000 Bin packing with discrete item sizes. I: Perfect packing theorems and the average case behavior of optimal packings. Zbl 0951.68192 Coffman, E. G. jun.; Courcoubetis, C.; Garey, M. R.; Johnson, D. S.; Shor, P. W. 8 2000 On the sum-of-squares algorithm for bin packing. Zbl 1296.68076 Csirik, Janos; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 7 2000 What are the least tractable instances of max independent set? Zbl 0929.68089 Johnson, David S.; Szegedy, Mario 15 1999 The maximum traveling salesman problem under polyhedral norms. Zbl 0910.90259 Barvinok, Alexander; Johnson, David S.; Woeginger, Gerhard J.; Woodroofe, Russell 22 1998 The traveling salesman problem: A case study. Zbl 0947.90612 Johnson, David S.; McGeoch, Lyle A. 122 1997 Bin packing with discrete item sizes. II: Tight bounds on first fit. Zbl 0899.90137 Coffman, E. G. jun.; Johnson, D. S.; Shor, P. W.; Weber, R. R. 4 1997 Introduction to the second DIMACS challenge: Cliques, coloring, and satisfiability. Zbl 0875.68678 Johnson, David S.; Trick, Michael A. 86 1996 Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Zbl 0845.90123 Johnson, D. S.; McGeoch, L. A.; Rothberg, E. E. 37 1996 Cliques, coloring, and satisfiability. Second DIMACS implementation challenge. Proceedings of a workshop held at DIMACS, October 11–13, 1993. Zbl 0851.00080 21 1996 Data structures for traveling salesmen. Zbl 0829.90132 Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G. 18 1995 The complexity of multiterminal cuts. Zbl 0809.68075 Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. 224 1994 Minimizing channel density by lateral shifting of components. Zbl 1114.68607 Johnson, D. S.; LaPaugh, A. S.; Pinter, R. Y. 1 1994 Network flows and matching. 1st DIMACS Implementation Challenge. Zbl 0781.00013 12 1993 Markov chains, computer proofs, and average-case analysis of best fit bin packing. Zbl 1310.68271 Coffman, E. G.; Johnson, D. S.; Shor, P. W.; Weber, R. R. 7 1993 Data structures for traveling salesmen. Zbl 0801.68032 Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G. 2 1993 The NP-completeness column: An ongoing guide. XXIII. Zbl 0786.68035 Johnson, David S. 3 1992 Probabilistic analysis of packing and related partitioning problems. Zbl 0770.90031 Coffman, E. G. jun.; Johnson, D. S.; Shor, P. W.; Lueker, G. S. 2 1992 Optimization by simulated annealing: An experimental evaluation. II: Graph coloring and number partitioning. Zbl 0739.90055 Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 133 1991 Bounded space on-line bin packing: Best is better than first. Zbl 0800.68478 Csirik, J.; Johnson, D. S. 7 1991 Unit disk graphs. Zbl 0739.05079 Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. 239 1990 A catalog of complexity classes. Zbl 0900.68246 Johnson, David S. 148 1990 Local optimization and the traveling salesman problem. Zbl 0766.90079 Johnson, David S. 62 1990 Generalized planar matching. Zbl 0731.68041 Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry 19 1990 The NP-completeness column: An ongoing guide. Zbl 0694.68035 Johnson, David S. 1 1990 Optimization by simulated annealing: An experimental evaluation. I: Graph partitioning. Zbl 0698.90065 Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 202 1989 On generating all maximal independent sets. Zbl 0654.68086 Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. 207 1988 How easy is local search? Zbl 0655.68074 Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 166 1988 The complexity of searching a graph. Zbl 0637.68081 Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. 123 1988 The NP-completeness column: An ongoing guide. XXI. Zbl 0651.68054 Johnson, David S. 5 1988 The NP-completeness column: An ongoing guide. XX. Zbl 0633.68022 Johnson, David S. 25 1987 Hypergraph planarity and the complexity of drawing Venn diagrams. Zbl 0654.05055 Johnson, D. S.; Pollak, H. O. 20 1987 The NP-completeness column: An ongoing guide. XIX. Zbl 0626.68039 Johnson, David S. 18 1987 The computational complexity of inferring rooted phylogenies by parsimony. Zbl 0607.92002 Day, William H. E.; Johnson, David S.; Sankoff, David 20 1986 The NP-completeness column: An ongoing guide. XVII. Zbl 0608.68033 Johnson, David S. 5 1986 The NP-completeness column: An ongoing guide. XVIII. Zbl 0626.68038 Johnson, David S. 2 1986 The NP-completeness column: An ongoing guide. XVI. Zbl 0608.68032 Johnson, David S. 112 1985 Scheduling file transfers. Zbl 0604.68039 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Lapaugh, A. S. 38 1985 A 71/60 theorem for bin packing. Zbl 0604.68046 Johnson, David S.; Garey, Michael R. 22 1985 Performance guarantees for heuristics. Zbl 0574.90086 Johnson, D. S.; Papadimitriou, C. H. 20 1985 The NP-completeness column: an ongoing guide. XIV. Zbl 0562.68032 Johnson, David S. 11 1985 The NP-completeness column: An ongoing guide. Zbl 0588.68020 Johnson, David S. 9 1985 Computational complexity. Zbl 0578.90087 Johnson, D. S.; Papadimitriou, C. H. 5 1985 Composing functions to minimize image size. Zbl 0602.68093 Garey, M. R.; Johnson, D. S. 1 1985 Approximation algorithms for bin-packing - an updated survey. Zbl 0558.68062 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 117 1984 On a dual version of the one-dimensional bin packing problem. Zbl 0556.68011 Assmann, S. F.; Johnson, D. S.; Kleitman, D. J.; Leung, J. Y.-T. 57 1984 Testing containment of conjunctive queries under functional and inclusion dependencies. Zbl 0563.68081 Johnson, D. S.; Klug, A. 42 1984 The NP-completeness column: An ongoing guide. XI. Zbl 0546.68025 Johnson, David S. 18 1984 The NP-completeness column: An ongoing guide. X. Zbl 0545.68032 Johnson, David S. 18 1984 The NP-completeness column: An ongoing guide. XII. Zbl 0547.68048 Johnson, David S. 4 1984 The NP-completeness column: an ongoing guide. XIII. Zbl 0562.68031 Johnson, David S. 1 1984 Crossing number is NP-complete. Zbl 0536.05016 Garey, M. R.; Johnson, D. S. 168 1983 On knapsacks, partitions, and a new dynamic programming technique for trees. Zbl 0506.90035 Johnson, D. S.; Niemi, K. A. 60 1983 Dynamic bin packing. Zbl 0512.68050 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 30 1983 Scheduling opposing forests. Zbl 0507.68021 Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M. 21 1983 The NP-completeness column: an ongoing guide. VII. Zbl 0509.68035 Johnson, David S. 8 1983 The NP-completeness column: an ongoing guide. IX. Zbl 0532.68050 Johnson, David S. 7 1983 Optimizing conjunctive queries that contain untyped variables. Zbl 0524.68059 Johnson, D. S.; Klug, A. 5 1983 The NP-completeness column: an ongoing guide. VI. Zbl 0509.68034 Johnson, David S. 2 1983 The NP-completeness column: An ongoing guide. VIII. Zbl 0524.68029 Johnson, David S. 2 1983 On packing two-dimensional bins. Zbl 0495.05016 Chung, F. R. K.; Garey, M. R.; Johnson, D. S. 59 1982 The NP-completeness column: An ongoing guide. III. Zbl 0494.68049 Johnson, David S. 25 1982 Computers and intractability. Transl. from the English by E. V. Levner and M. A. Frumkin. (Вычислителъные машины и труднорешаемые задачи.) Zbl 0522.68040 Garey, Michael R.; Johnson, David S. 17 1982 The complexity of the generalized Lloyd-Max problem. Zbl 0476.94009 Garey, M. R.; Johnson, D. S.; Witsenhausen, Hans S. 11 1982 The NP-completeness column: An ongoing guide. II. Zbl 0494.68048 Johnson, David S. 11 1982 The NP-completeness column: An ongoing guide. IV. Zbl 0494.68050 Johnson, David S. 11 1982 The NP-completeness column: An ongoing guide. V. Zbl 0502.68007 Johnson, David S. 9 1982 Scheduling unit-time tasks with arbitrary release times and deadlines. Zbl 0472.68021 Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E. 40 1981 The NP-completeness column: An ongoing guide. I. Zbl 0494.68047 Johnson, David S. 22 1981 Performance bounds for level-oriented two-dimensional packing algorithms. Zbl 0447.68079 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Tarjan, R. E. 109 1980 The complexity of coloring circular arcs and chords. Zbl 0499.05058 Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. 108 1980 Computers and intractability. A guide to the theory of NP-completeness. Zbl 0411.68039 Garey, Michael R.; Johnson, David S. 9,485 1979 “Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035 Garey, M. R.; Johnson, D. S. 233 1978 An application of bin-packing to multiprocessor scheduling. Zbl 0374.68032 Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 129 1978 Complexity results for bandwidth minimization. Zbl 0385.05048 Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E. 109 1978 The complexity of the network design problem. Zbl 0395.94048 Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G. 86 1978 Triangulating a simple polygon. Zbl 0384.68040 Garey, Michael R.; Johnson, David S.; Preparata, Franco P.; Tarjan, Robert E. 59 1978 The densest hemisphere problem. Zbl 0368.68053 Johnson, D. S.; Preparata, F. P. 37 1978 Performance guarantees for scheduling algorithms. Zbl 0371.90068 Garey, M. R.; Graham, R. L.; Johnson, D. S. 19 1978 Two results concerning multicoloring. Zbl 0374.05025 Chvatal, V.; Garey, M. R.; Johnson, D. S. 10 1978 Problems. Zbl 0379.05001 2 1978 ...and 22 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 16,066 Authors 118 Woeginger, Gerhard 78 Golovach, Petr A. 73 Epstein, Leah 67 Paulusma, Daniël 66 Pardalos, Panos M. 65 Cheng, Tai-Chiu Edwin 61 Fomin, Fedor V. 59 Jansen, Klaus 58 Niedermeier, Rolf 53 Yuan, Jinjiang 52 Bodlaender, Hans L. 49 Monnot, Jérôme 48 Kratsch, Dieter 48 Paschos, Vangelis Th. 44 Kovalëv, Mikhail Yakovlevich 44 Lin, Guohui 42 Chen, Jian-er 42 Saurabh, Saket 41 Leung, Joseph Y.-T. 40 Levin, Asaf 40 Thilikos, Dimitrios M. 39 Błażewicz, Jacek 38 Boysen, Nils 38 de Werra, Dominique 38 Ibaraki, Toshihide 36 Ito, Takehiro 34 Dósa, György 34 Fellows, Michael Ralph 34 Heggernes, Pinar 34 Papadimitriou, Christos Harilaos 34 Rothe, Jörg-Matthias 34 Tuza, Zsolt 33 Makino, Kazuhisa 32 Boros, Endre 32 Otachi, Yota 32 Yang, Boting 31 de Figueiredo, Celina M. Herrera 31 Gottlob, Georg 31 Nagamochi, Hiroshi 31 Szwarcfiter, Jayme Luiz 31 Zhang, Guochuan 30 Brandstädt, Andreas 30 Du, Ding-Zhu 30 Lingas, Andrzej 29 Fernau, Henning 29 Ono, Hirotaka 29 Zhang, Zhao 28 Pesch, Erwin 27 Hansen, Pierre 26 Gutin, Gregory Z. 26 Hao, Jin-Kao 26 Ravi, S. S. 26 Sau, Ignasi 26 Spieksma, Frits C. R. 26 Uehara, Ryuhei 26 van ’t Hof, Pim 26 Wu, Weili 25 Broersma, Hajo J. 25 Escoffier, Bruno 25 Kel’manov, Aleksandr Vasil’evich 25 Lokshtanov, Daniel 25 Rautenbach, Dieter 25 Yannakakis, Mihalis 25 Zehavi, Meirav 24 Bazgan, Cristina 24 Demaine, Erik D. 24 Demange, Marc 24 Dourado, Mitre Costa 24 Lin, Bertrand Miao-Tsong 24 Ng, C. T. Daniel 24 Rizzi, Romeo 23 Guo, Jiong 23 Halldórsson, Magnús Mar 23 Kellerer, Johann 23 Kratochvíl, Jan 23 Krumke, Sven Oliver 23 Kubiak, Wiesław X. 23 Marathe, Madhav V. 23 Pyatkin, Artëm Valer’evich 23 Rajasingh, Indra 23 Ries, Bernard 23 Wang, Jianxin 22 Eiter, Thomas 22 Han, Xin 22 Hell, Pavol 22 Jacobson, Sheldon H. 22 Laporte, Gilbert 22 Li, Jianping 22 Prokopyev, Oleg Alexan 22 Serna Iglesias, Maria José 22 Sriskandarajah, Chelliah 22 Werner, Frank 22 Yeo, Anders 22 Zhu, Binhai 21 Glover, Fred W. 21 Grigorev, Aleksandr 21 Gupta, Jatinder N. D. 21 Hedetniemi, Stephen Travis 21 Hertz, Alain 21 Lee, Chung-Yee ...and 15,966 more Authors all top 5 Cited in 588 Serials 1,178 Discrete Applied Mathematics 1,176 Theoretical Computer Science 1,084 European Journal of Operational Research 565 Information Processing Letters 563 Computers & Operations Research 457 Algorithmica 336 Discrete Mathematics 314 Journal of Combinatorial Optimization 293 Journal of Computer and System Sciences 289 Operations Research Letters 257 Annals of Operations Research 231 Artificial Intelligence 210 Networks 197 Journal of Scheduling 184 Mathematical Programming. Series A. Series B 139 Discrete Optimization 123 Information and Computation 115 Journal of Discrete Algorithms 112 Theory of Computing Systems 108 Computational Geometry 101 Optimization Letters 98 Journal of Global Optimization 90 Information Sciences 82 Discrete Mathematics, Algorithms and Applications 78 Annals of Mathematics and Artificial Intelligence 73 International Journal of Foundations of Computer Science 71 SIAM Journal on Discrete Mathematics 66 International Transactions in Operational Research 64 Applied Mathematics and Computation 62 Discrete & Computational Geometry 61 International Journal of Computer Mathematics 60 Journal of Graph Theory 59 RAIRO. Operations Research 57 Acta Informatica 57 Graphs and Combinatorics 56 Naval Research Logistics 56 European Journal of Combinatorics 55 Journal of Heuristics 54 Journal of Combinatorial Theory. Series B 54 SIAM Journal on Algebraic and Discrete Methods 54 International Journal of Production Research 52 Computers & Mathematics with Applications 52 Computational Optimization and Applications 43 Computing 43 Mathematical and Computer Modelling 39 SIAM Journal on Computing 39 Linear Algebra and its Applications 37 Journal of Optimization Theory and Applications 37 Applied Mathematical Modelling 36 International Journal of Computational Geometry & Applications 36 Diskretnyĭ Analiz i Issledovanie Operatsiĭ 35 Asia-Pacific Journal of Operational Research 35 INFORMS Journal on Computing 35 Mathematical Problems in Engineering 33 Discussiones Mathematicae. Graph Theory 32 Annals of Pure and Applied Logic 32 Journal of Parallel and Distributed Computing 30 Natural Computing 30 4OR 30 Algorithms 29 Constraints 27 Automatica 27 OR Spectrum 26 Mathematical Social Sciences 26 Combinatorica 25 Journal of Complexity 25 International Journal of Approximate Reasoning 25 Applied Mathematics Letters 25 Mathematical Methods of Operations Research 24 Acta Mathematicae Applicatae Sinica. English Series 23 Mathematical Programming 23 Computational Complexity 23 The Electronic Journal of Combinatorics 23 Journal of Graph Algorithms and Applications 22 Journal of Symbolic Computation 22 Automation and Remote Control 22 JMMA. Journal of Mathematical Modelling and Algorithms 21 Optimization 21 Journal of Mathematical Sciences (New York) 21 Mathematical Programming Computation 20 Journal of Computer and Systems Sciences International 19 BIT 19 Fuzzy Sets and Systems 19 Real-Time Systems 19 Cybernetics and Systems Analysis 19 Optimization Methods & Software 19 AKCE International Journal of Graphs and Combinatorics 19 Computer Science Review 18 Journal of Information & Optimization Sciences 18 Random Structures & Algorithms 18 Distributed Computing 17 Journal of Discrete Mathematical Sciences & Cryptography 17 Proceedings of the Steklov Institute of Mathematics 16 Journal of Combinatorial Theory. Series A 16 Mathematical Systems Theory 15 OR Spektrum 15 Order 15 Journal of Computer Science and Technology 15 Journal of Automated Reasoning 15 Games and Economic Behavior ...and 488 more Serials all top 5 Cited in 54 Fields 7,563 Computer science (68-XX) 6,269 Operations research, mathematical programming (90-XX) 4,359 Combinatorics (05-XX) 700 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 410 Numerical analysis (65-XX) 351 Mathematical logic and foundations (03-XX) 309 Information and communication theory, circuits (94-XX) 289 Biology and other natural sciences (92-XX) 213 Convex and discrete geometry (52-XX) 162 Statistics (62-XX) 113 Order, lattices, ordered algebraic structures (06-XX) 104 Systems theory; control (93-XX) 85 Linear and multilinear algebra; matrix theory (15-XX) 82 Number theory (11-XX) 80 Probability theory and stochastic processes (60-XX) 80 Quantum theory (81-XX) 64 Group theory and generalizations (20-XX) 50 Calculus of variations and optimal control; optimization (49-XX) 43 Statistical mechanics, structure of matter (82-XX) 39 Geometry (51-XX) 32 Dynamical systems and ergodic theory (37-XX) 31 General algebraic systems (08-XX) 24 Commutative algebra (13-XX) 20 Manifolds and cell complexes (57-XX) 17 Field theory and polynomials (12-XX) 16 General and overarching topics; collections (00-XX) 16 Algebraic geometry (14-XX) 12 Associative rings and algebras (16-XX) 12 General topology (54-XX) 12 Mechanics of deformable solids (74-XX) 10 Mechanics of particles and systems (70-XX) 9 History and biography (01-XX) 8 Measure and integration (28-XX) 8 Approximations and expansions (41-XX) 6 Category theory; homological algebra (18-XX) 6 Functions of a complex variable (30-XX) 6 Ordinary differential equations (34-XX) 6 Functional analysis (46-XX) 6 Operator theory (47-XX) 5 Real functions (26-XX) 5 Partial differential equations (35-XX) 4 Differential geometry (53-XX) 4 Classical thermodynamics, heat transfer (80-XX) 4 Geophysics (86-XX) 3 Algebraic topology (55-XX) 3 Fluid mechanics (76-XX) 2 Relativity and gravitational theory (83-XX) 2 Mathematics education (97-XX) 1 Topological groups, Lie groups (22-XX) 1 Potential theory (31-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Optics, electromagnetic theory (78-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.