David S. Johnson

Cited by

	All	Since 2017
Citations	192831	41091
h-index	107	63
i10-index	321	157

9000

4500

2250

6750

1983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022507 593 647 717 765 901 1126 1351 1362 1622 1940 2208 2443 2420 2718 2820 2806 2970 4154 5186 6416 7201 7675 8028 8426 8081 7965 7824 7786 7875 7830 7378 7271 7631 7473 7759 7680 7561 7831 2754

Public access

View all

37 articles

4 articles

available

not available

Based on funding mandates

Co-authors

E. G. Coffman, Jr.RetiredVerified email at cs.columbia.edu
Mihalis YannakakisPercy K. and Vida L. W. Hudson Professor of Computer Science, Columbia UniversityVerified email at cs.columbia.edu
Michael TrickDean, Carnegie Mellon University in QatarVerified email at cmu.edu
Cecilia AragonProfessor of Human Centered Design & Engineering, University of WashingtonVerified email at uw.edu
Catherine SchevonColumbia UniversityVerified email at columbia.edu
Ravi SethiProfessor, Computer Science, The University of ArizonaVerified email at email.arizona.edu
Gerhard WoegingerProfessor of Computer Science, RWTH AachenVerified email at cs.rwth-aachen.de
Jeffrey Ullman Professor of Computer Science, Stanford UniversityVerified email at stanford.edu
Jennifer RexfordProfessor of Computer Science, Princeton UniversityVerified email at cs.princeton.edu
Weixiong ZhangProfessor of Computer Science and of Genetics, Washington UniversityVerified email at cse.wustl.edu
Howard KarloffGoldman SachsVerified email at cc.gatech.edu
Jia WangIEEE Fellow, Lead Inventive Scientist, AT&T Labs - ResearchVerified email at att.com
Costas CourcoubetisProfessor in SDS, CUHK ShenzhenVerified email at cuhk.edu.cn
Martin SucharaComputational Scientist, Argonne National LaboratoryVerified email at anl.gov
Jill CirasellaThe Graduate Center, CUNYVerified email at gc.cuny.edu
Zygmunt J. HaasCornell UniversityVerified email at ee.cornell.edu
Z. Morley Mao (茅斫青)University of MichiganVerified email at umich.edu
Suresh VenkatasubramanianSchool of Computing, University of UtahVerified email at cs.utah.edu
Shankar KrishnanGoogle ResearchVerified email at google.com
G. GutinProfessor of Computer Science, Royal Holloway, University of LondonVerified email at rhul.ac.uk

David S. Johnson

Visiting Professor, Columbia University Computer Science Department

Verified email at research.att.com - Homepage

Algorithms computer science optimization traveling salesman problem bin packing


Title Sort by citations Sort by year Sort by title	Cited by Cited by	Year
Computers and intractability MR Garey, DS Johnson freeman, 1979	73347	1979
Initial sequencing and analysis of the human genome ES Lander, LM Linton, B Birren, C Nusbaum, MC Zody, J Baldwin, ... Macmillan Publishers Ltd., 2001	27997	2001
Mobility support in IPv6 D Johnson, C Perkins, J Arkko RFC 3775, june 6 (30), 2004, 2004	8075	2004
Initial sequencing and comparative analysis of the mouse genome RH Waterston, L Pachter Nature 420 (6915), 520-562, 2002	7905	2002
Estimating the reproducibility of psychological science Open Science Collaboration Science 349 (6251), aac4716, 2015	6561	2015
Some simplified NP-complete problems MR Garey, DS Johnson, L Stockmeyer Proceedings of the sixth annual ACM symposium on Theory of computing, 47-63, 1974	3517	1974
The complexity of flowshop and jobshop scheduling MR Garey, DS Johnson, R Sethi Mathematics of operations research 1 (2), 117-129, 1976	3355	1976
Approximation algorithms for combinatorial problems DS Johnson Journal of computer and system sciences 9 (3), 256-278, 1974	3166	1974
Chemotherapy in non-small cell lung cancer: a meta-analysis using updated data on individual patients from 52 randomised clinical trials Non-small Cell Lung Cancer Collaborative Group Bmj 311 (7010), 899-909, 1995	3152	1995
Optimization by simulated annealing: An experimental evaluation; part I, graph partitioning DS Johnson, CR Aragon, LA McGeoch, C Schevon Operations research 37 (6), 865-892, 1989	2775*	1989
Approximation algorithms for bin packing: A survey EGC man Jr, MR Garey, DS Johnson Approximation algorithms for NP-hard problems, 46-93, 1996	2042*	1996
The traveling salesman problem: A case study in local optimization DS Johnson, LA McGeoch Local search in combinatorial optimization 1 (1), 215-310, 1997	1867	1997
Unit disk graphs BN Clark, CJ Colbourn, DS Johnson Discrete mathematics 86 (1-3), 165-177, 1990	1776	1990
The genome of the social amoeba Dictyostelium discoideum L Eichinger, JA Pachebat, G Glöckner, MA Rajandream, R Sucgang, ... Nature 435 (7038), 43-57, 2005	1507	2005
Computers and Intractability: A Guide to the Theory of NP-completeness MR Gary, DS Johnson WH Freeman and Company, New York, 1979	1454	1979
The Rectilinear Steiner Tree Problem is -Complete MR Garey, DS Johnson SIAM Journal on Applied Mathematics 32 (4), 826-834, 1977	1445	1977
Worst-case performance bounds for simple one-dimensional packing algorithms DS Johnson, A Demers, JD Ullman, MR Garey, RL Graham SIAM Journal on computing 3 (4), 299-325, 1974	1187	1974
Crossing number is NP-complete MR Garey, DS Johnson SIAM Journal on Algebraic Discrete Methods 4 (3), 312-316, 1983	1061	1983
On generating all maximal independent sets DS Johnson, M Yannakakis, CH Papadimitriou Information Processing Letters 27 (3), 119-123, 1988	977	1988
The NP-completeness column: an ongoing guide DS Johnson Journal of algorithms 6 (3), 434-451, 1985	920*	1985

The system can't perform the operation now. Try again later.

Articles 1–20

Citations per year

Duplicate citations

Merged citations

Add co-authorsCo-authors

Follow this author

Cited by

Co-authors