Edit Profile Johnson, David Stifler Compute Distance To: Compute Author ID: johnson.david-stifler Published as: Johnson, D. S.; Johnson, David; Johnson, David S.; Johnson, David Stifler Homepage: http://davidsjohnson.net/ External Links: MGP · Wikidata · dblp · GND Documents Indexed: 127 Publications since 1973, including 7 Books Biographic References: 2 Publications all top 5 Co-Authors 34 single-authored 41 Garey, Michael Randolph 10 Coffman, Edward Grady jun. 9 McGeoch, Lyle A. 8 Shor, Peter Williston 7 Graham, Ronald Lewis 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 Hajiaghayi, Mohammad Taghi 2 Klug, Alena 2 LaPaugh, Andrea S. 2 McGeoch, Catherine C. 2 Orlin, James B. 2 Ostheimer, Gretchen 2 Pollak, Henry O. 2 Preparata, Franco P. 2 Resende, Mauricio G. C. 2 Schevon, Catherine A. 2 Sen, Subhabrata 2 Trick, Michael A. 2 Woeginger, Gerhard Johannes 2 Zhang, Weixiong 1 Applegate, David A. 1 Assmann, Susan F. 1 Berman, Fran 1 Boyce, William M. 1 Brucker, Peter J. 1 Calinescu, Gruia 1 Chung Graham, Fan-Rong King 1 Chvátal, Vašek 1 Cirasella, Jill 1 Clark, Brent N. 1 Colbourn, Charles J. 1 Dahlhaus, Elias 1 Day, William H. E. 1 Demers, Alan J. 1 Demetrescu, Camil 1 Epstein, Leah 1 Fekete, Sándor P. 1 Gelles, Ran 1 Goldberg, Andrew V. 1 Goldwasser, Michael H. 1 Gutin, Gregory Z. 1 Hakimi, Seifollah Louis 1 Hwang, Frank Kwangming 1 Kleitman, Daniel J. 1 Knuth, Donald Ervin 1 Leighton, Tom 1 Lenstra, Jan Karel 1 Leung, Joseph Y.-T. 1 Levin, Asaf 1 Ligett, Katrina 1 Lueker, George S. 1 Megiddo, Nimrod 1 Miller, Gordon L. 1 Minkoff, Maria 1 Niemi, K. A. 1 Nishizeki, Takao 1 Nozaki, Akihiro 1 Phillips, Steven J. 1 Pinter, Ron Yair 1 Rinnooy Kan, Alexander Hendrik George 1 Rothberg, E. E. 1 Sankoff, David 1 Sethi, Ravi 1 Seymour, Paul D. 1 Simons, Barbara B. 1 Snyder, Larry E. 1 So, Hing-Cheung 1 Stockmeyer, Larry J. 1 Szegedy, Mario 1 Tamir, Arie 1 Ullman, Jeffrey David 1 Wang, Jia 1 Wilf, Herbert S. 1 Witsenhausen, Hans S. 1 Woodroofe, Russ 1 Woodroofe, Russell 1 Yao, Andrew Chi-Chih 1 Yeo, Anders 1 Zverovitch, Alexei 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 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 all top 5 Fields 101 Computer science (68-XX) 49 Operations research, mathematical programming (90-XX) 34 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 117 Publications have been cited 14,114 times in 11,815 Documents Cited by ▼ Year ▼ Computers and intractability. A guide to the theory of NP-completeness. Zbl 0411.68039Garey, Michael R.; Johnson, David S. 8,318 1979 Some simplified NP-complete graph problems. Zbl 0338.05120Garey, M. R.; Johnson, D. S.; Stockmeyer, L. 557 1976 The complexity of flow shop and jobshop scheduling. Zbl 0396.90041Garey, M. R.; Johnson, D. S.; Sethi, Ravi 328 1976 Approximation algorithms for combinatorial problems. Zbl 0296.65036Johnson, David S. 328 1974 “Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035Garey, M. R.; Johnson, D. S. 211 1978 The rectilinear Steiner tree problem is NP-complete. Zbl 0396.05009Garey, M. R.; Johnson, D. S. 199 1977 Optimization by simulated annealing: An experimental evaluation. I: Graph partitioning. Zbl 0698.90065Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 182 1989 The complexity of multiterminal cuts. Zbl 0809.68075Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. 170 1994 Worst-case performance bounds for simple one-dimensional packing algorithms. Zbl 0297.68028Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L. 169 1975 Unit disk graphs. Zbl 0739.05079Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. 167 1990 On generating all maximal independent sets. Zbl 0654.68086Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. 156 1988 A catalog of complexity classes. Zbl 0900.68246Johnson, David S. 136 1990 How easy is local search? Zbl 0655.68074Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 127 1988 Optimization by simulated annealing: An experimental evaluation. II: Graph coloring and number partitioning. Zbl 0739.90055Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 126 1991 The planar Hamiltonian circuit problem is NP-complete. Zbl 0346.05110Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre 126 1976 Crossing number is NP-complete. Zbl 0536.05016Garey, M. R.; Johnson, D. S. 120 1983 An application of bin-packing to multiprocessor scheduling. Zbl 0374.68032Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 111 1978 The complexity of computing Steiner minimal trees. Zbl 0399.05023Garey, M. R.; Graham, R. L.; Johnson, D. S. 109 1977 The complexity of searching a graph. Zbl 0637.68081Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. 103 1988 The traveling salesman problem: A case study. Zbl 0947.90612Johnson, David S.; McGeoch, Lyle A. 102 1997 Approximation algorithms for bin-packing - an updated survey. Zbl 0558.68062Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 101 1984 Fast algorithms for bin packing. Zbl 0284.68023Johnson, David S. 101 1974 Complexity results for bandwidth minimization. Zbl 0385.05048Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E. 100 1978 Two-processor scheduling with start-times and deadlines. Zbl 0369.90053Garey, M. R.; Johnson, D. S. 99 1977 The NP-completeness column: An ongoing guide. XVI. Zbl 0608.68032Johnson, David S. 91 1985 The complexity of coloring circular arcs and chords. Zbl 0499.05058Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. 86 1980 Performance bounds for level-oriented two-dimensional packing algorithms. Zbl 0447.68079Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Tarjan, R. E. 86 1980 Complexity results for multiprocessor scheduling under resource constraints. Zbl 0365.90076Garey, M. R.; Johnson, D. S. 74 1975 The complexity of the network design problem. Zbl 0395.94048Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G. 71 1978 Introduction to the second DIMACS challenge: Cliques, coloring, and satisfiability. Zbl 0875.68678Johnson, David S.; Trick, Michael A. 66 1996 Resource constrained scheduling as generalized bin packing. Zbl 0384.90053Garey, M. R.; Graham, R. L.; Johnson, D. S.; Yao, Andrew Chi-Chih 59 1976 The complexity of near-optimal graph coloring. Zbl 0322.05111Garey, M. R.; Johnson, D. S. 53 1976 Local optimization and the traveling salesman problem. Zbl 0766.90079Johnson, David S. 51 1990 On a dual version of the one-dimensional bin packing problem. Zbl 0556.68011Assmann, S. F.; Johnson, D. S.; Kleitman, D. J.; Leung, J. Y.-T. 50 1984 On packing two-dimensional bins. Zbl 0495.05016Chung, F. R. K.; Garey, M. R.; Johnson, D. S. 50 1982 Triangulating a simple polygon. Zbl 0384.68040Garey, Michael R.; Johnson, David S.; Preparata, Franco P.; Tarjan, Robert E. 50 1978 On knapsacks, partitions, and a new dynamic programming technique for trees. Zbl 0506.90035Johnson, D. S.; Niemi, K. A. 49 1983 The prize collecting Steiner tree problem: Theory and practice. Zbl 0956.68112Johnson, David S.; Minkoff, Maria; Phillips, Steven 48 2000 Experimental analysis of heuristics for the STSP. Zbl 1113.90356Johnson, David S.; McGeoch, Lyle A. 47 2002 Some NP-complete geometric problems. Zbl 0377.68036Garey, M. R.; Graham, R. L.; Johnson, D. S. 47 1976 Scheduling file transfers. Zbl 0604.68039Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Lapaugh, A. S. 37 1985 Testing containment of conjunctive queries under functional and inclusion dependencies. Zbl 0563.68081Johnson, D. S.; Klug, A. 36 1984 Scheduling unit-time tasks with arbitrary release times and deadlines. Zbl 0472.68021Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E. 35 1981 Scheduling tasks with nonuniform deadlines on two processors. Zbl 0338.68048Garey, M. R.; Johnson, D. S. 33 1976 Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Zbl 0845.90123Johnson, D. S.; McGeoch, L. A.; Rothberg, E. E. 32 1996 The densest hemisphere problem. Zbl 0368.68053Johnson, D. S.; Preparata, F. P. 29 1978 Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Zbl 0397.90044Brucker, Peter; Garey, M. R.; Johnson, D. S. 26 1977 An application of graph coloring to printed circuit testing. Zbl 0342.94021Garey, Michael R.; Johnson, David Stifler; So, Hing C. 25 1976 Experimental analysis of heuristics for the ATSP. Zbl 1113.90355Johnson, David S.; Gutin, Gregory; McGeoch, Lyle A.; Yeo, Anders; Zhang, Weixiong; Zverovitch, Alexei 22 2002 The computational complexity of inferring rooted phylogenies by parsimony. Zbl 0607.92002Day, William H. E.; Johnson, David S.; Sankoff, David 22 1986 Dynamic bin packing. Zbl 0512.68050Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 22 1983 The NP-completeness column: An ongoing guide. III. Zbl 0494.68049Johnson, David S. 22 1982 The maximum traveling salesman problem under polyhedral norms. Zbl 0910.90259Barvinok, Alexander; Johnson, David S.; Woeginger, Gerhard J.; Woodroofe, Russell 21 1998 Cliques, coloring, and satisfiability. Second DIMACS implementation challenge. Proceedings of a workshop held at DIMACS, October 11–13, 1993. Zbl 0851.00080Johnson, David S. (ed.); Trick, Michael A. (ed.) 21 1996 The NP-completeness column: An ongoing guide. I. Zbl 0494.68047Johnson, David S. 21 1981 The NP-completeness column: An ongoing guide. XX. Zbl 0633.68022Johnson, David S. 20 1987 Scheduling opposing forests. Zbl 0507.68021Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M. 20 1983 The NP-completeness column: An ongoing guide. X. Zbl 0545.68032Johnson, David S. 19 1984 Performance guarantees for scheduling algorithms. Zbl 0371.90068Garey, M. R.; Graham, R. L.; Johnson, D. S. 19 1978 The asymmetric traveling salesman problem: algorithms, instance generators, and tests. Zbl 1010.68848Cirasella, Jill; Johnson, David S.; McGeoch, Lyle A.; Zhang, Weixiong 18 2001 Better approximation algorithms for bin covering. Zbl 1018.90037Csirik, Janos; Johnson, David S.; Kenyon, Claire 17 2001 Performance guarantees for heuristics. Zbl 0574.90086Johnson, D. S.; Papadimitriou, C. H. 17 1985 A theoretician’s guide to the experimental analysis of algorithms. Zbl 1103.68997Johnson, David S. 16 2002 Data structures for traveling salesmen. Zbl 0829.90132Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G. 15 1995 A 71/60 theorem for bin packing. Zbl 0604.68046Johnson, David S.; Garey, Michael R. 15 1985 The NP-completeness column: An ongoing guide. II. Zbl 0494.68048Johnson, David S. 15 1982 Bounded space on-line bin packing: Best is better than first. Zbl 0980.68141Csirik, J.; Johnson, D. S. 14 2001 Generalized planar matching. Zbl 0731.68041Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry 14 1990 Hypergraph planarity and the complexity of drawing Venn diagrams. Zbl 0654.05055Johnson, D. S.; Pollak, H. O. 13 1987 The NP-completeness column: An ongoing guide. XIX. Zbl 0626.68039Johnson, David S. 12 1987 The NP-completeness column: An ongoing guide. XI. Zbl 0546.68025Johnson, David S. 12 1984 Approximation algorithms for combinatorial problems: An annotated bibliography. Zbl 0382.05001Garey, M. R.; Johnson, D. S. 12 1976 Approximation algorithms for combinatorial problems. Zbl 0316.68024Johnson, David S. 12 1973 The NP-completeness column: An ongoing guide. IV. Zbl 0494.68050Johnson, David S. 11 1982 Worst case behavior of graph coloring algorithms. Zbl 0308.05109Johnson, David S. 11 1974 What are the least tractable instances of max independent set? Zbl 0929.68089Johnson, David S.; Szegedy, Mario 10 1999 The NP-completeness column. Zbl 1442.68065Johnson, David S. (ed.) 9 2005 Network flows and matching. 1st DIMACS Implementation Challenge. Zbl 0781.00013Johnson, David S. (ed.); McGeoch, Catherine C. (ed.) 9 1993 The NP-completeness column: An ongoing guide. Zbl 0588.68020Johnson, David S. 9 1985 Two results concerning multicoloring. Zbl 0374.05025Chvatal, V.; Garey, M. R.; Johnson, D. S. 9 1978 The NP-completeness column: an ongoing guide. XIV. Zbl 0562.68032Johnson, David S. 8 1985 The shortest path problem. Ninth DIMACS implementation challenge, Piscataway, NJ, USA, November 13–14, 2006. Proceedings. Zbl 1172.05005Demetrescu, Camil (ed.); Goldberg, Andrew V. (ed.); Johnson, David S. (ed.) 7 2009 The geometric maximum traveling salesman problem. Zbl 1325.90074Barvinok, Alexander; Fekete, Sándor P.; Johnson, David S.; Tamir, Arie; Woeginger, Gerhard J.; Woodroofe, Russ 7 2003 On the sum-of-squares algorithm for bin packing. Zbl 1296.68076Csirik, Janos; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 7 2000 Bin packing with discrete item sizes. I: Perfect packing theorems and the average case behavior of optimal packings. Zbl 0951.68192Coffman, E. G. jun.; Courcoubetis, C.; Garey, M. R.; Johnson, D. S.; Shor, P. W. 7 2000 Bounded space on-line bin packing: Best is better than first. Zbl 0800.68478Csirik, J.; Johnson, D. S. 7 1991 The NP-completeness column: an ongoing guide. VII. Zbl 0509.68035Johnson, David S. 7 1983 The NP-completeness column: An ongoing guide. V. Zbl 0502.68007Johnson, David S. 7 1982 The NP-completeness column: an ongoing guide. IX. Zbl 0532.68050Johnson, David S. 6 1983 The complexity of the generalized Lloyd-Max problem. Zbl 0476.94009Garey, M. R.; Johnson, D. S.; Witsenhausen, Hans S. 6 1982 Markov chains, computer proofs, and average-case analysis of best fit bin packing. Zbl 1310.68271Coffman, E. G.; Johnson, D. S.; Shor, P. W.; Weber, R. R. 5 1993 The NP-completeness column: An ongoing guide. XVII. Zbl 0608.68033Johnson, David S. 5 1986 Computational complexity. Zbl 0578.90087Johnson, D. S.; Papadimitriou, C. H. 5 1985 The NP-completeness column: An ongoing guide. XII. Zbl 0547.68048Johnson, David S. 5 1984 Optimizing conjunctive queries that contain untyped variables. Zbl 0524.68059Johnson, D. S.; Klug, A. 5 1983 The NP-completeness column: finding needles in haystacks. Zbl 1445.68103Johnson, David S. (ed.) 4 2007 On the sum-of-squares algorithm for bin packing. Zbl 1326.68334Csirik, János; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 4 2006 Computers and intractability. (Vychislitel’nye mashiny i trudnoreshaemye zadachi). Transl. from the English by E. V. Levner and M. A. Frumkin. Zbl 0522.68040Garey, Michael R.; Johnson, David S. 4 1982 Resource-based corruptions and the combinatorics of hidden diversity. Zbl 1364.94537Garay, Juan; Johnson, David; Kiayias, Aggelos; Yung, Moti 3 2013 Bin packing with discrete item sizes. II: Tight bounds on first fit. Zbl 0899.90137Coffman, E. G. jun.; Johnson, D. S.; Shor, P. W.; Weber, R. R. 3 1997 Resource-based corruptions and the combinatorics of hidden diversity. Zbl 1364.94537Garay, Juan; Johnson, David; Kiayias, Aggelos; Yung, Moti 3 2013 Disjoint-path facility location: theory and practice. Zbl 1429.68185Breslau, Lee; Diakonikolas, Ilias; Duffield, Nick; Gu, Yu; Hajiaghayi, Mohammad Taghi; Johnson, David S.; Karloff, Howard; Resende, Mauricio G. C.; Sen, Subhabrata 1 2011 The shortest path problem. Ninth DIMACS implementation challenge, Piscataway, NJ, USA, November 13–14, 2006. Proceedings. Zbl 1172.05005Demetrescu, Camil (ed.); Goldberg, Andrew V. (ed.); Johnson, David S. (ed.) 7 2009 The NP-completeness column: finding needles in haystacks. Zbl 1445.68103Johnson, David S. (ed.) 4 2007 Compressing rectilinear pictures and minimizing access control lists. Zbl 1302.68297Applegate, David A.; Calinescu, Gruia; Johnson, David S.; Karloff, Howard; Ligett, Katrina; Wang, Jia 1 2007 On the sum-of-squares algorithm for bin packing. Zbl 1326.68334Csirik, János; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 4 2006 The NP-completeness column. Zbl 1442.68065Johnson, David S. (ed.) 9 2005 The geometric maximum traveling salesman problem. Zbl 1325.90074Barvinok, Alexander; Fekete, Sándor P.; Johnson, David S.; Tamir, Arie; Woeginger, Gerhard J.; Woodroofe, Russ 7 2003 Experimental analysis of heuristics for the STSP. Zbl 1113.90356Johnson, David S.; McGeoch, Lyle A. 47 2002 Experimental analysis of heuristics for the ATSP. Zbl 1113.90355Johnson, David S.; Gutin, Gregory; McGeoch, Lyle A.; Yeo, Anders; Zhang, Weixiong; Zverovitch, Alexei 22 2002 A theoretician’s guide to the experimental analysis of algorithms. Zbl 1103.68997Johnson, David S. 16 2002 Perfect packing theorems and the average-case behavior of optimal and online bin packing. Zbl 0999.68260Coffman, 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.68848Cirasella, Jill; Johnson, David S.; McGeoch, Lyle A.; Zhang, Weixiong 18 2001 Better approximation algorithms for bin covering. Zbl 1018.90037Csirik, Janos; Johnson, David S.; Kenyon, Claire 17 2001 Bounded space on-line bin packing: Best is better than first. Zbl 0980.68141Csirik, J.; Johnson, D. S. 14 2001 The prize collecting Steiner tree problem: Theory and practice. Zbl 0956.68112Johnson, David S.; Minkoff, Maria; Phillips, Steven 48 2000 On the sum-of-squares algorithm for bin packing. Zbl 1296.68076Csirik, Janos; Johnson, David S.; Kenyon, Claire; Orlin, James B.; Shor, Peter W.; Weber, Richard R. 7 2000 Bin packing with discrete item sizes. I: Perfect packing theorems and the average case behavior of optimal packings. Zbl 0951.68192Coffman, E. G. jun.; Courcoubetis, C.; Garey, M. R.; Johnson, D. S.; Shor, P. W. 7 2000 What are the least tractable instances of max independent set? Zbl 0929.68089Johnson, David S.; Szegedy, Mario 10 1999 The maximum traveling salesman problem under polyhedral norms. Zbl 0910.90259Barvinok, Alexander; Johnson, David S.; Woeginger, Gerhard J.; Woodroofe, Russell 21 1998 The traveling salesman problem: A case study. Zbl 0947.90612Johnson, David S.; McGeoch, Lyle A. 102 1997 Bin packing with discrete item sizes. II: Tight bounds on first fit. Zbl 0899.90137Coffman, E. G. jun.; Johnson, D. S.; Shor, P. W.; Weber, R. R. 3 1997 Introduction to the second DIMACS challenge: Cliques, coloring, and satisfiability. Zbl 0875.68678Johnson, David S.; Trick, Michael A. 66 1996 Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Zbl 0845.90123Johnson, D. S.; McGeoch, L. A.; Rothberg, E. E. 32 1996 Cliques, coloring, and satisfiability. Second DIMACS implementation challenge. Proceedings of a workshop held at DIMACS, October 11–13, 1993. Zbl 0851.00080Johnson, David S. (ed.); Trick, Michael A. (ed.) 21 1996 Data structures for traveling salesmen. Zbl 0829.90132Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G. 15 1995 The complexity of multiterminal cuts. Zbl 0809.68075Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. 170 1994 Minimizing channel density by lateral shifting of components. Zbl 1114.68607Johnson, D. S.; LaPaugh, A. S.; Pinter, R. Y. 1 1994 Network flows and matching. 1st DIMACS Implementation Challenge. Zbl 0781.00013Johnson, David S. (ed.); McGeoch, Catherine C. (ed.) 9 1993 Markov chains, computer proofs, and average-case analysis of best fit bin packing. Zbl 1310.68271Coffman, E. G.; Johnson, D. S.; Shor, P. W.; Weber, R. R. 5 1993 Data structures for traveling salesmen. Zbl 0801.68032Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G. 1 1993 Probabilistic analysis of packing and related partitioning problems. Zbl 0770.90031Coffman, E. G. jun.; Johnson, D. S.; Shor, P. W.; Lueker, G. S. 2 1992 The NP-completeness column: An ongoing guide. XXIII. Zbl 0786.68035Johnson, David S. 2 1992 Optimization by simulated annealing: An experimental evaluation. II: Graph coloring and number partitioning. Zbl 0739.90055Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 126 1991 Bounded space on-line bin packing: Best is better than first. Zbl 0800.68478Csirik, J.; Johnson, D. S. 7 1991 Unit disk graphs. Zbl 0739.05079Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. 167 1990 A catalog of complexity classes. Zbl 0900.68246Johnson, David S. 136 1990 Local optimization and the traveling salesman problem. Zbl 0766.90079Johnson, David S. 51 1990 Generalized planar matching. Zbl 0731.68041Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry 14 1990 The NP-completeness column: An ongoing guide. Zbl 0694.68035Johnson, David S. 1 1990 Optimization by simulated annealing: An experimental evaluation. I: Graph partitioning. Zbl 0698.90065Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine 182 1989 On generating all maximal independent sets. Zbl 0654.68086Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. 156 1988 How easy is local search? Zbl 0655.68074Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 127 1988 The complexity of searching a graph. Zbl 0637.68081Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. 103 1988 The NP-completeness column: An ongoing guide. XXI. Zbl 0651.68054Johnson, David S. 3 1988 The NP-completeness column: An ongoing guide. XX. Zbl 0633.68022Johnson, David S. 20 1987 Hypergraph planarity and the complexity of drawing Venn diagrams. Zbl 0654.05055Johnson, D. S.; Pollak, H. O. 13 1987 The NP-completeness column: An ongoing guide. XIX. Zbl 0626.68039Johnson, David S. 12 1987 The computational complexity of inferring rooted phylogenies by parsimony. Zbl 0607.92002Day, William H. E.; Johnson, David S.; Sankoff, David 22 1986 The NP-completeness column: An ongoing guide. XVII. Zbl 0608.68033Johnson, David S. 5 1986 The NP-completeness column: An ongoing guide. XVIII. Zbl 0626.68038Johnson, David S. 1 1986 The NP-completeness column: An ongoing guide. XVI. Zbl 0608.68032Johnson, David S. 91 1985 Scheduling file transfers. Zbl 0604.68039Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Lapaugh, A. S. 37 1985 Performance guarantees for heuristics. Zbl 0574.90086Johnson, D. S.; Papadimitriou, C. H. 17 1985 A 71/60 theorem for bin packing. Zbl 0604.68046Johnson, David S.; Garey, Michael R. 15 1985 The NP-completeness column: An ongoing guide. Zbl 0588.68020Johnson, David S. 9 1985 The NP-completeness column: an ongoing guide. XIV. Zbl 0562.68032Johnson, David S. 8 1985 Computational complexity. Zbl 0578.90087Johnson, D. S.; Papadimitriou, C. H. 5 1985 Composing functions to minimize image size. Zbl 0602.68093Garey, M. R.; Johnson, D. S. 1 1985 Approximation algorithms for bin-packing - an updated survey. Zbl 0558.68062Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 101 1984 On a dual version of the one-dimensional bin packing problem. Zbl 0556.68011Assmann, S. F.; Johnson, D. S.; Kleitman, D. J.; Leung, J. Y.-T. 50 1984 Testing containment of conjunctive queries under functional and inclusion dependencies. Zbl 0563.68081Johnson, D. S.; Klug, A. 36 1984 The NP-completeness column: An ongoing guide. X. Zbl 0545.68032Johnson, David S. 19 1984 The NP-completeness column: An ongoing guide. XI. Zbl 0546.68025Johnson, David S. 12 1984 The NP-completeness column: An ongoing guide. XII. Zbl 0547.68048Johnson, David S. 5 1984 The NP-completeness column: an ongoing guide. XIII. Zbl 0562.68031Johnson, David S. 1 1984 Crossing number is NP-complete. Zbl 0536.05016Garey, M. R.; Johnson, D. S. 120 1983 On knapsacks, partitions, and a new dynamic programming technique for trees. Zbl 0506.90035Johnson, D. S.; Niemi, K. A. 49 1983 Dynamic bin packing. Zbl 0512.68050Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 22 1983 Scheduling opposing forests. Zbl 0507.68021Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M. 20 1983 The NP-completeness column: an ongoing guide. VII. Zbl 0509.68035Johnson, David S. 7 1983 The NP-completeness column: an ongoing guide. IX. Zbl 0532.68050Johnson, David S. 6 1983 Optimizing conjunctive queries that contain untyped variables. Zbl 0524.68059Johnson, D. S.; Klug, A. 5 1983 The NP-completeness column: An ongoing guide. VIII. Zbl 0524.68029Johnson, David S. 2 1983 The NP-completeness column: an ongoing guide. VI. Zbl 0509.68034Johnson, David S. 2 1983 On packing two-dimensional bins. Zbl 0495.05016Chung, F. R. K.; Garey, M. R.; Johnson, D. S. 50 1982 The NP-completeness column: An ongoing guide. III. Zbl 0494.68049Johnson, David S. 22 1982 The NP-completeness column: An ongoing guide. II. Zbl 0494.68048Johnson, David S. 15 1982 The NP-completeness column: An ongoing guide. IV. Zbl 0494.68050Johnson, David S. 11 1982 The NP-completeness column: An ongoing guide. V. Zbl 0502.68007Johnson, David S. 7 1982 The complexity of the generalized Lloyd-Max problem. Zbl 0476.94009Garey, M. R.; Johnson, D. S.; Witsenhausen, Hans S. 6 1982 Computers and intractability. (Vychislitel’nye mashiny i trudnoreshaemye zadachi). Transl. from the English by E. V. Levner and M. A. Frumkin. Zbl 0522.68040Garey, Michael R.; Johnson, David S. 4 1982 Scheduling unit-time tasks with arbitrary release times and deadlines. Zbl 0472.68021Garey, M. R.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E. 35 1981 The NP-completeness column: An ongoing guide. I. Zbl 0494.68047Johnson, David S. 21 1981 The complexity of coloring circular arcs and chords. Zbl 0499.05058Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. 86 1980 Performance bounds for level-oriented two-dimensional packing algorithms. Zbl 0447.68079Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Tarjan, R. E. 86 1980 Computers and intractability. A guide to the theory of NP-completeness. Zbl 0411.68039Garey, Michael R.; Johnson, David S. 8,318 1979 “Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035Garey, M. R.; Johnson, D. S. 211 1978 An application of bin-packing to multiprocessor scheduling. Zbl 0374.68032Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S. 111 1978 Complexity results for bandwidth minimization. Zbl 0385.05048Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E. 100 1978 The complexity of the network design problem. Zbl 0395.94048Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G. 71 1978 Triangulating a simple polygon. Zbl 0384.68040Garey, Michael R.; Johnson, David S.; Preparata, Franco P.; Tarjan, Robert E. 50 1978 The densest hemisphere problem. Zbl 0368.68053Johnson, D. S.; Preparata, F. P. 29 1978 Performance guarantees for scheduling algorithms. Zbl 0371.90068Garey, M. R.; Graham, R. L.; Johnson, D. S. 19 1978 Two results concerning multicoloring. Zbl 0374.05025Chvatal, V.; Garey, M. R.; Johnson, D. S. 9 1978 On a number-theoretic bin packing conjecture. Zbl 0399.05019Garey, M. R.; Graham, R. L.; Johnson, D. S. 2 1978 A note on bisecting minimum spanning trees. Zbl 0387.05005Boyce, W. M.; Garey, M. R.; Johnson, D. S. 1 1978 The rectilinear Steiner tree problem is NP-complete. Zbl 0396.05009Garey, M. R.; Johnson, D. S. 199 1977 The complexity of computing Steiner minimal trees. Zbl 0399.05023Garey, M. R.; Graham, R. L.; Johnson, D. S. 109 1977 Two-processor scheduling with start-times and deadlines. Zbl 0369.90053Garey, M. R.; Johnson, D. S. 99 1977 ...and 17 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 13,877 Authors 105 Woeginger, Gerhard Johannes 65 Cheng, Tai-Chiu Edwin 59 Pardalos, Panos M. 58 Golovach, Petr A. 57 Epstein, Leah 56 Paulusma, Daniël 49 Yuan, Jinjiang 48 Paschos, Vangelis Th. 46 Fomin, Fedor V. 45 Jansen, Klaus 44 Bodlaender, Hans L. 43 Kratsch, Dieter 43 Niedermeier, Rolf 42 Monnot, Jérôme 41 Leung, Joseph Y.-T. 40 de Werra, Dominique 38 Błażewicz, Jacek 37 Thilikos, Dimitrios M. 36 Chen, Jian-er 36 Papadimitriou, Christos Harilaos 35 Ibaraki, Toshihide 35 Levin, Asaf 34 Kovalyov, Mikhail Yakovlevich 33 Fellows, Michael Ralph 30 Boros, Endre 30 Du, Ding-Zhu 30 Heggernes, Pinar 30 Hertz, Alain 30 Lin, Guohui 30 Tuza, Zsolt 29 Gottlob, Georg 29 Makino, Kazuhisa 27 Brandstädt, Andreas 27 Hansen, Pierre 27 Lingas, Andrzej 27 Nagamochi, Hiroshi 26 de Figueiredo, Celina M. Herrera 26 Dósa, György 26 Yannakakis, Mihalis 26 Zhang, Guochuan 25 Gutin, Gregory Z. 25 Lin, Bertrand Miao-Tsong 25 Saurabh, Saket 24 Boysen, Nils 24 Ito, Takehiro 24 Kel’manov, Aleksandr Vasil’evich 24 Szwarcfiter, Jayme Luiz 23 Gupta, Jatinder N. D. 23 Hao, Jin-Kao 23 Hedetniemi, Stephen Travis 23 Spieksma, Frits C. R. 23 Wu, Weili 22 Broersma, Hajo J. 22 Demaine, Erik D. 22 Demange, Marc 22 Escoffier, Bruno 22 Fernau, Henning 22 Kellerer, Johann 22 Kratochvíl, Jan 22 Ono, Hirotaka 22 Pesch, Erwin 22 Ravi, S. S. 22 Sau, Ignasi 22 van ’t Hof, Pim 21 Bazgan, Cristina 21 Eiter, Thomas 21 Guo, Jiong 21 Jacobson, Sheldon H. 21 Krumke, Sven Oliver 21 Laporte, Gilbert 21 Otachi, Yota 21 Rautenbach, Dieter 21 Rothe, Jörg-Matthias 21 Sriskandarajah, Chelliah 21 Werner, Frank 21 Yang, Boting 21 Zhang, Zhao 20 Dell’Olmo, Paolo 20 Han, Xin 20 Hassin, Refael 20 Hell, Pavol 20 Kubiak, Wiesław X. 20 Lee, Chung-Yee 20 Peleg, David 20 Picouleau, Christophe 20 Rajasingh, Indra 20 Ries, Bernard 20 Serna, Maria José 20 Wang, Jianxin 20 Yeo, Anders 19 Colbourn, Charles J. 19 Glover, Fred W. 19 Maffioli, Francesco 19 Pyatkin, Artem V. 19 Rizzi, Romeo 19 Steiner, George 19 Tang, Chuan Yi 18 Chang, Gerard Jennhwa 18 Della Croce, Federico 18 Dereniowski, Dariusz ...and 13,777 more Authors all top 5 Cited in 491 Serials 1,158 Discrete Applied Mathematics 1,133 Theoretical Computer Science 1,024 European Journal of Operational Research 565 Information Processing Letters 509 Computers & Operations Research 370 Algorithmica 341 Discrete Mathematics 287 Journal of Computer and System Sciences 287 Operations Research Letters 234 Annals of Operations Research 232 Journal of Combinatorial Optimization 199 Artificial Intelligence 176 Journal of Scheduling 174 Networks 159 Mathematical Programming. Series A. Series B 135 Discrete Optimization 122 Journal of Discrete Algorithms 119 Information and Computation 101 Theory of Computing Systems 99 Computational Geometry 86 Journal of Global Optimization 77 Information Sciences 70 Annals of Mathematics and Artificial Intelligence 64 Optimization Letters 63 Computers & Mathematics with Applications 61 International Journal of Computer Mathematics 60 International Journal of Foundations of Computer Science 57 RAIRO. Operations Research 56 Journal of Combinatorial Theory. Series B 55 Applied Mathematics and Computation 54 Acta Informatica 54 SIAM Journal on Algebraic and Discrete Methods 54 International Journal of Production Research 53 Discrete & Computational Geometry 53 Journal of Heuristics 51 European Journal of Combinatorics 50 SIAM Journal on Discrete Mathematics 48 Computational Optimization and Applications 48 Discrete Mathematics, Algorithms and Applications 47 Mathematical and Computer Modelling 46 Journal of Graph Theory 44 Naval Research Logistics 43 Graphs and Combinatorics 42 Computing 39 Linear Algebra and its Applications 34 International Journal of Computational Geometry & Applications 32 Journal of Parallel and Distributed Computing 32 Mathematical Problems in Engineering 31 Journal of Optimization Theory and Applications 31 Annals of Pure and Applied Logic 31 Applied Mathematical Modelling 30 Algorithms 28 Asia-Pacific Journal of Operational Research 27 Journal of Complexity 27 Applied Mathematics Letters 26 Automatica 26 International Transactions in Operational Research 25 Mathematical Social Sciences 25 Combinatorica 25 Acta Mathematicae Applicatae Sinica. English Series 25 International Journal of Approximate Reasoning 24 Constraints 23 Mathematical Programming 23 Journal of Symbolic Computation 23 Discussiones Mathematicae. Graph Theory 22 JMMA. Journal of Mathematical Modelling and Algorithms 21 Computational Complexity 21 Natural Computing 19 BIT 19 Fuzzy Sets and Systems 19 SIAM Journal on Computing 19 Optimization 19 Real-Time Systems 19 Mathematical Methods of Operations Research 19 Diskretnyĭ Analiz i Issledovanie Operatsiĭ 18 Journal of Information & Optimization Sciences 18 Journal of Computer and Systems Sciences International 18 Journal of Mathematical Sciences (New York) 18 4OR 18 Computer Science Review 17 Journal of Combinatorial Theory. Series A 17 Advances in Applied Mathematics 17 Automation and Remote Control 16 Mathematical Systems Theory 16 Games and Economic Behavior 16 Mathematical Programming Computation 15 OR Spektrum 15 Order 15 Journal of Computer Science and Technology 15 Journal of Automated Reasoning 15 Random Structures & Algorithms 15 Distributed Computing 15 RAIRO. Informatique Théorique et Applications 15 Doklady Mathematics 15 Journal of Graph Algorithms and Applications 15 OR Spectrum 15 Proceedings of the Steklov Institute of Mathematics 14 Journal of Mathematical Psychology 14 Systems & Control Letters 14 Pattern Recognition ...and 391 more Serials all top 5 Cited in 54 Fields 6,256 Computer science (68-XX) 5,334 Operations research, mathematical programming (90-XX) 3,556 Combinatorics (05-XX) 547 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 400 Numerical analysis (65-XX) 330 Mathematical logic and foundations (03-XX) 263 Biology and other natural sciences (92-XX) 252 Information and communication theory, circuits (94-XX) 187 Convex and discrete geometry (52-XX) 126 Statistics (62-XX) 103 Systems theory; control (93-XX) 94 Order, lattices, ordered algebraic structures (06-XX) 69 Probability theory and stochastic processes (60-XX) 68 Linear and multilinear algebra; matrix theory (15-XX) 63 Number theory (11-XX) 60 Group theory and generalizations (20-XX) 51 Quantum theory (81-XX) 41 Calculus of variations and optimal control; optimization (49-XX) 33 Geometry (51-XX) 31 General algebraic systems (08-XX) 30 Statistical mechanics, structure of matter (82-XX) 27 Dynamical systems and ergodic theory (37-XX) 20 Commutative algebra (13-XX) 18 Manifolds and cell complexes (57-XX) 17 Field theory and polynomials (12-XX) 15 General and overarching topics; collections (00-XX) 13 Algebraic geometry (14-XX) 12 Associative rings and algebras (16-XX) 12 General topology (54-XX) 11 Mechanics of deformable solids (74-XX) 9 History and biography (01-XX) 8 Approximations and expansions (41-XX) 8 Mechanics of particles and systems (70-XX) 6 Real functions (26-XX) 6 Measure and integration (28-XX) 6 Operator theory (47-XX) 5 Functions of a complex variable (30-XX) 5 Ordinary differential equations (34-XX) 4 Functional analysis (46-XX) 4 Differential geometry (53-XX) 4 Geophysics (86-XX) 3 Category theory; homological algebra (18-XX) 3 Partial differential equations (35-XX) 3 Classical thermodynamics, heat transfer (80-XX) 2 Several complex variables and analytic spaces (32-XX) 2 Algebraic topology (55-XX) 2 Fluid mechanics (76-XX) 2 Relativity and gravitational theory (83-XX) 1 Topological groups, Lie groups (22-XX) 1 Potential theory (31-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Optics, electromagnetic theory (78-XX) 1 Mathematics education (97-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.