×

zbMATH — the first resource for mathematics

Johnson, David Stifler

Compute Distance To:
Author ID: johnson.david-stifler Recent zbMATH articles by "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

Publications by Year

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.68039
Garey, Michael R.; Johnson, David S.
1979
Some simplified NP-complete graph problems. Zbl 0338.05120
Garey, M. R.; Johnson, D. S.; Stockmeyer, L.
557
1976
The complexity of flow shop and jobshop scheduling. Zbl 0396.90041
Garey, M. R.; Johnson, D. S.; Sethi, Ravi
328
1976
Approximation algorithms for combinatorial problems. Zbl 0296.65036
Johnson, David S.
328
1974
“Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035
Garey, M. R.; Johnson, D. S.
211
1978
The rectilinear Steiner tree problem is NP-complete. Zbl 0396.05009
Garey, M. R.; Johnson, D. S.
199
1977
Optimization by simulated annealing: An experimental evaluation. I: Graph partitioning. Zbl 0698.90065
Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine
182
1989
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, 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.68028
Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L.
169
1975
Unit disk graphs. Zbl 0739.05079
Clark, Brent N.; Colbourn, Charles J.; Johnson, David S.
167
1990
On generating all maximal independent sets. Zbl 0654.68086
Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H.
156
1988
A catalog of complexity classes. Zbl 0900.68246
Johnson, David S.
136
1990
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
127
1988
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
126
1991
The planar Hamiltonian circuit problem is NP-complete. Zbl 0346.05110
Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre
126
1976
Crossing number is NP-complete. Zbl 0536.05016
Garey, M. R.; Johnson, D. S.
120
1983
An application of bin-packing to multiprocessor scheduling. Zbl 0374.68032
Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.
111
1978
The complexity of computing Steiner minimal trees. Zbl 0399.05023
Garey, M. R.; Graham, R. L.; Johnson, D. S.
109
1977
The complexity of searching a graph. Zbl 0637.68081
Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H.
103
1988
The traveling salesman problem: A case study. Zbl 0947.90612
Johnson, David S.; McGeoch, Lyle A.
102
1997
Approximation algorithms for bin-packing - an updated survey. Zbl 0558.68062
Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.
101
1984
Fast algorithms for bin packing. Zbl 0284.68023
Johnson, David S.
101
1974
Complexity results for bandwidth minimization. Zbl 0385.05048
Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E.
100
1978
Two-processor scheduling with start-times and deadlines. Zbl 0369.90053
Garey, M. R.; Johnson, D. S.
99
1977
The NP-completeness column: An ongoing guide. XVI. Zbl 0608.68032
Johnson, David S.
91
1985
The complexity of coloring circular arcs and chords. Zbl 0499.05058
Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H.
86
1980
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.
86
1980
Complexity results for multiprocessor scheduling under resource constraints. Zbl 0365.90076
Garey, M. R.; Johnson, D. S.
74
1975
The complexity of the network design problem. Zbl 0395.94048
Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G.
71
1978
Introduction to the second DIMACS challenge: Cliques, coloring, and satisfiability. Zbl 0875.68678
Johnson, David S.; Trick, Michael A.
66
1996
Resource constrained scheduling as generalized bin packing. Zbl 0384.90053
Garey, M. R.; Graham, R. L.; Johnson, D. S.; Yao, Andrew Chi-Chih
59
1976
The complexity of near-optimal graph coloring. Zbl 0322.05111
Garey, M. R.; Johnson, D. S.
53
1976
Local optimization and the traveling salesman problem. Zbl 0766.90079
Johnson, David S.
51
1990
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.
50
1984
On packing two-dimensional bins. Zbl 0495.05016
Chung, F. R. K.; Garey, M. R.; Johnson, D. S.
50
1982
Triangulating a simple polygon. Zbl 0384.68040
Garey, 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.90035
Johnson, D. S.; Niemi, K. A.
49
1983
The prize collecting Steiner tree problem: Theory and practice. Zbl 0956.68112
Johnson, David S.; Minkoff, Maria; Phillips, Steven
48
2000
Experimental analysis of heuristics for the STSP. Zbl 1113.90356
Johnson, David S.; McGeoch, Lyle A.
47
2002
Some NP-complete geometric problems. Zbl 0377.68036
Garey, M. R.; Graham, R. L.; Johnson, D. S.
47
1976
Scheduling file transfers. Zbl 0604.68039
Coffman, 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.68081
Johnson, D. S.; Klug, A.
36
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.
35
1981
Scheduling tasks with nonuniform deadlines on two processors. Zbl 0338.68048
Garey, M. R.; Johnson, D. S.
33
1976
Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Zbl 0845.90123
Johnson, D. S.; McGeoch, L. A.; Rothberg, E. E.
32
1996
The densest hemisphere problem. Zbl 0368.68053
Johnson, D. S.; Preparata, F. P.
29
1978
Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Zbl 0397.90044
Brucker, Peter; Garey, M. R.; Johnson, D. S.
26
1977
An application of graph coloring to printed circuit testing. Zbl 0342.94021
Garey, Michael R.; Johnson, David Stifler; So, Hing C.
25
1976
Experimental analysis of heuristics for the ATSP. Zbl 1113.90355
Johnson, 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.92002
Day, William H. E.; Johnson, David S.; Sankoff, David
22
1986
Dynamic bin packing. Zbl 0512.68050
Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.
22
1983
The NP-completeness column: An ongoing guide. III. Zbl 0494.68049
Johnson, David S.
22
1982
The maximum traveling salesman problem under polyhedral norms. Zbl 0910.90259
Barvinok, 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.00080
Johnson, David S. (ed.); Trick, Michael A. (ed.)
21
1996
The NP-completeness column: An ongoing guide. I. Zbl 0494.68047
Johnson, David S.
21
1981
The NP-completeness column: An ongoing guide. XX. Zbl 0633.68022
Johnson, David S.
20
1987
Scheduling opposing forests. Zbl 0507.68021
Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M.
20
1983
The NP-completeness column: An ongoing guide. X. Zbl 0545.68032
Johnson, David S.
19
1984
Performance guarantees for scheduling algorithms. Zbl 0371.90068
Garey, M. R.; Graham, R. L.; Johnson, D. S.
19
1978
The asymmetric traveling salesman problem: algorithms, instance generators, and tests. Zbl 1010.68848
Cirasella, Jill; Johnson, David S.; McGeoch, Lyle A.; Zhang, Weixiong
18
2001
Better approximation algorithms for bin covering. Zbl 1018.90037
Csirik, Janos; Johnson, David S.; Kenyon, Claire
17
2001
Performance guarantees for heuristics. Zbl 0574.90086
Johnson, D. S.; Papadimitriou, C. H.
17
1985
A theoretician’s guide to the experimental analysis of algorithms. Zbl 1103.68997
Johnson, David S.
16
2002
Data structures for traveling salesmen. Zbl 0829.90132
Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G.
15
1995
A 71/60 theorem for bin packing. Zbl 0604.68046
Johnson, David S.; Garey, Michael R.
15
1985
The NP-completeness column: An ongoing guide. II. Zbl 0494.68048
Johnson, David S.
15
1982
Bounded space on-line bin packing: Best is better than first. Zbl 0980.68141
Csirik, J.; Johnson, D. S.
14
2001
Generalized planar matching. Zbl 0731.68041
Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry
14
1990
Hypergraph planarity and the complexity of drawing Venn diagrams. Zbl 0654.05055
Johnson, D. S.; Pollak, H. O.
13
1987
The NP-completeness column: An ongoing guide. XIX. Zbl 0626.68039
Johnson, David S.
12
1987
The NP-completeness column: An ongoing guide. XI. Zbl 0546.68025
Johnson, David S.
12
1984
Approximation algorithms for combinatorial problems: An annotated bibliography. Zbl 0382.05001
Garey, M. R.; Johnson, D. S.
12
1976
Approximation algorithms for combinatorial problems. Zbl 0316.68024
Johnson, David S.
12
1973
The NP-completeness column: An ongoing guide. IV. Zbl 0494.68050
Johnson, David S.
11
1982
Worst case behavior of graph coloring algorithms. Zbl 0308.05109
Johnson, David S.
11
1974
What are the least tractable instances of max independent set? Zbl 0929.68089
Johnson, David S.; Szegedy, Mario
10
1999
The NP-completeness column. Zbl 1442.68065
Johnson, David S. (ed.)
9
2005
Network flows and matching. 1st DIMACS Implementation Challenge. Zbl 0781.00013
Johnson, David S. (ed.); McGeoch, Catherine C. (ed.)
9
1993
The NP-completeness column: An ongoing guide. Zbl 0588.68020
Johnson, David S.
9
1985
Two results concerning multicoloring. Zbl 0374.05025
Chvatal, V.; Garey, M. R.; Johnson, D. S.
9
1978
The NP-completeness column: an ongoing guide. XIV. Zbl 0562.68032
Johnson, David S.
8
1985
The shortest path problem. Ninth DIMACS implementation challenge, Piscataway, NJ, USA, November 13–14, 2006. Proceedings. Zbl 1172.05005
Demetrescu, Camil (ed.); Goldberg, Andrew V. (ed.); Johnson, David S. (ed.)
7
2009
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
7
2003
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
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.
7
2000
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. VII. Zbl 0509.68035
Johnson, David S.
7
1983
The NP-completeness column: An ongoing guide. V. Zbl 0502.68007
Johnson, David S.
7
1982
The NP-completeness column: an ongoing guide. IX. Zbl 0532.68050
Johnson, David S.
6
1983
The complexity of the generalized Lloyd-Max problem. Zbl 0476.94009
Garey, 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.68271
Coffman, E. G.; Johnson, D. S.; Shor, P. W.; Weber, R. R.
5
1993
The NP-completeness column: An ongoing guide. XVII. Zbl 0608.68033
Johnson, David S.
5
1986
Computational complexity. Zbl 0578.90087
Johnson, D. S.; Papadimitriou, C. H.
5
1985
The NP-completeness column: An ongoing guide. XII. Zbl 0547.68048
Johnson, David S.
5
1984
Optimizing conjunctive queries that contain untyped variables. Zbl 0524.68059
Johnson, D. S.; Klug, A.
5
1983
The NP-completeness column: finding needles in haystacks. Zbl 1445.68103
Johnson, David S. (ed.)
4
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.
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.68040
Garey, Michael R.; Johnson, David S.
4
1982
Resource-based corruptions and the combinatorics of hidden diversity. Zbl 1364.94537
Garay, Juan; Johnson, David; Kiayias, Aggelos; Yung, Moti
3
2013
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.
3
1997
Resource-based corruptions and the combinatorics of hidden diversity. Zbl 1364.94537
Garay, Juan; Johnson, David; Kiayias, Aggelos; Yung, Moti
3
2013
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
1
2011
The shortest path problem. Ninth DIMACS implementation challenge, Piscataway, NJ, USA, November 13–14, 2006. Proceedings. Zbl 1172.05005
Demetrescu, Camil (ed.); Goldberg, Andrew V. (ed.); Johnson, David S. (ed.)
7
2009
The NP-completeness column: finding needles in haystacks. Zbl 1445.68103
Johnson, David S. (ed.)
4
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
1
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.
4
2006
The NP-completeness column. Zbl 1442.68065
Johnson, David S. (ed.)
9
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
7
2003
Experimental analysis of heuristics for the STSP. Zbl 1113.90356
Johnson, David S.; McGeoch, Lyle A.
47
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
22
2002
A theoretician’s guide to the experimental analysis of algorithms. Zbl 1103.68997
Johnson, David S.
16
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
18
2001
Better approximation algorithms for bin covering. Zbl 1018.90037
Csirik, Janos; Johnson, David S.; Kenyon, Claire
17
2001
Bounded space on-line bin packing: Best is better than first. Zbl 0980.68141
Csirik, J.; Johnson, D. S.
14
2001
The prize collecting Steiner tree problem: Theory and practice. Zbl 0956.68112
Johnson, David S.; Minkoff, Maria; Phillips, Steven
48
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
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.
7
2000
What are the least tractable instances of max independent set? Zbl 0929.68089
Johnson, David S.; Szegedy, Mario
10
1999
The maximum traveling salesman problem under polyhedral norms. Zbl 0910.90259
Barvinok, Alexander; Johnson, David S.; Woeginger, Gerhard J.; Woodroofe, Russell
21
1998
The traveling salesman problem: A case study. Zbl 0947.90612
Johnson, David S.; McGeoch, Lyle A.
102
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.
3
1997
Introduction to the second DIMACS challenge: Cliques, coloring, and satisfiability. Zbl 0875.68678
Johnson, David S.; Trick, Michael A.
66
1996
Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Zbl 0845.90123
Johnson, 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.00080
Johnson, David S. (ed.); Trick, Michael A. (ed.)
21
1996
Data structures for traveling salesmen. Zbl 0829.90132
Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G.
15
1995
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.
170
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
Johnson, David S. (ed.); McGeoch, Catherine C. (ed.)
9
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.
5
1993
Data structures for traveling salesmen. Zbl 0801.68032
Fredman, M. L.; Johnson, D. S.; McGeoch, L. A.; Ostheimer, G.
1
1993
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
The NP-completeness column: An ongoing guide. XXIII. Zbl 0786.68035
Johnson, David 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
126
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.
167
1990
A catalog of complexity classes. Zbl 0900.68246
Johnson, David S.
136
1990
Local optimization and the traveling salesman problem. Zbl 0766.90079
Johnson, David S.
51
1990
Generalized planar matching. Zbl 0731.68041
Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry
14
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
182
1989
On generating all maximal independent sets. Zbl 0654.68086
Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H.
156
1988
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
127
1988
The complexity of searching a graph. Zbl 0637.68081
Megiddo, 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.68054
Johnson, David S.
3
1988
The NP-completeness column: An ongoing guide. XX. Zbl 0633.68022
Johnson, David S.
20
1987
Hypergraph planarity and the complexity of drawing Venn diagrams. Zbl 0654.05055
Johnson, D. S.; Pollak, H. O.
13
1987
The NP-completeness column: An ongoing guide. XIX. Zbl 0626.68039
Johnson, David S.
12
1987
The computational complexity of inferring rooted phylogenies by parsimony. Zbl 0607.92002
Day, William H. E.; Johnson, David S.; Sankoff, David
22
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.
1
1986
The NP-completeness column: An ongoing guide. XVI. Zbl 0608.68032
Johnson, David S.
91
1985
Scheduling file transfers. Zbl 0604.68039
Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Lapaugh, A. S.
37
1985
Performance guarantees for heuristics. Zbl 0574.90086
Johnson, D. S.; Papadimitriou, C. H.
17
1985
A 71/60 theorem for bin packing. Zbl 0604.68046
Johnson, David S.; Garey, Michael R.
15
1985
The NP-completeness column: An ongoing guide. Zbl 0588.68020
Johnson, David S.
9
1985
The NP-completeness column: an ongoing guide. XIV. Zbl 0562.68032
Johnson, David S.
8
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.
101
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.
50
1984
Testing containment of conjunctive queries under functional and inclusion dependencies. Zbl 0563.68081
Johnson, D. S.; Klug, A.
36
1984
The NP-completeness column: An ongoing guide. X. Zbl 0545.68032
Johnson, David S.
19
1984
The NP-completeness column: An ongoing guide. XI. Zbl 0546.68025
Johnson, David S.
12
1984
The NP-completeness column: An ongoing guide. XII. Zbl 0547.68048
Johnson, David S.
5
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.
120
1983
On knapsacks, partitions, and a new dynamic programming technique for trees. Zbl 0506.90035
Johnson, D. S.; Niemi, K. A.
49
1983
Dynamic bin packing. Zbl 0512.68050
Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.
22
1983
Scheduling opposing forests. Zbl 0507.68021
Garey, M. R.; Johnson, D. S.; Tarjan, R. E.; Yannakakis, M.
20
1983
The NP-completeness column: an ongoing guide. VII. Zbl 0509.68035
Johnson, David S.
7
1983
The NP-completeness column: an ongoing guide. IX. Zbl 0532.68050
Johnson, David S.
6
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. VIII. Zbl 0524.68029
Johnson, David S.
2
1983
The NP-completeness column: an ongoing guide. VI. Zbl 0509.68034
Johnson, David S.
2
1983
On packing two-dimensional bins. Zbl 0495.05016
Chung, F. R. K.; Garey, M. R.; Johnson, D. S.
50
1982
The NP-completeness column: An ongoing guide. III. Zbl 0494.68049
Johnson, David S.
22
1982
The NP-completeness column: An ongoing guide. II. Zbl 0494.68048
Johnson, David S.
15
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.
7
1982
The complexity of the generalized Lloyd-Max problem. Zbl 0476.94009
Garey, 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.68040
Garey, Michael R.; Johnson, David S.
4
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.
35
1981
The NP-completeness column: An ongoing guide. I. Zbl 0494.68047
Johnson, David S.
21
1981
The complexity of coloring circular arcs and chords. Zbl 0499.05058
Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H.
86
1980
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.
86
1980
Computers and intractability. A guide to the theory of NP-completeness. Zbl 0411.68039
Garey, Michael R.; Johnson, David S.
1979
“Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035
Garey, M. R.; Johnson, D. S.
211
1978
An application of bin-packing to multiprocessor scheduling. Zbl 0374.68032
Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.
111
1978
Complexity results for bandwidth minimization. Zbl 0385.05048
Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E.
100
1978
The complexity of the network design problem. Zbl 0395.94048
Johnson, D. S.; Lenstra, J. K.; Rinnooy Kan, A. H. G.
71
1978
Triangulating a simple polygon. Zbl 0384.68040
Garey, Michael R.; Johnson, David S.; Preparata, Franco P.; Tarjan, Robert E.
50
1978
The densest hemisphere problem. Zbl 0368.68053
Johnson, D. S.; Preparata, F. P.
29
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.
9
1978
On a number-theoretic bin packing conjecture. Zbl 0399.05019
Garey, M. R.; Graham, R. L.; Johnson, D. S.
2
1978
A note on bisecting minimum spanning trees. Zbl 0387.05005
Boyce, W. M.; Garey, M. R.; Johnson, D. S.
1
1978
The rectilinear Steiner tree problem is NP-complete. Zbl 0396.05009
Garey, M. R.; Johnson, D. S.
199
1977
The complexity of computing Steiner minimal trees. Zbl 0399.05023
Garey, M. R.; Graham, R. L.; Johnson, D. S.
109
1977
Two-processor scheduling with start-times and deadlines. Zbl 0369.90053
Garey, M. R.; Johnson, D. S.
99
1977
...and 17 more Documents
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.