David S. Johnson | Academic Influence

David S. Johnson's AcademicInfluence.com Rankings

David S. Johnson

Computer Science

#252

World Rank

#263

Historical Rank

#151

USA Rank

Database

#84

World Rank

#86

Historical Rank

#50

USA Rank

computer-science Degrees

Download Badge

Computer Science

David S. Johnson's Degrees

PhD Computer Science Stanford University
Masters Computer Science Stanford University

Similar Degrees You Can Earn

Why Is David S. Johnson Influential?

(Suggest an Edit or Addition)

According to Wikipedia, David Stifler Johnson was an American computer scientist specializing in algorithms and optimization. He was the head of the Algorithms and Optimization Department of AT&T Labs Research from 1988 to 2013, and was a visiting professor at Columbia University from 2014 to 2016. He was awarded the 2010 Knuth Prize.

(See a Problem?)

David S. Johnson's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Computers and Intractability: A Guide to the Theory of NP-Completeness (1978) (49523)
Computers and In stractability: A Guide to the Theory of NP-Completeness. W. H Freeman, San Fran (1979) (2818)
Approximation algorithms for combinatorial problems (1973) (2513)
The Complexity of Flowshop and Jobshop Scheduling (1976) (2421)
Some Simplified NP-Complete Graph Problems (1976) (2177)
Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning (1989) (1609)
Unit disk graphs (1991) (1456)
Approximation algorithms for bin packing: a survey (1996) (1109)
The Rectilinear Steiner Tree Problem is NP Complete (1977) (1065)
Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning (1991) (971)
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms (1974) (913)
On Generating All Maximal Independent Sets (1988) (833)
The Traveling Salesman Problem: A Case Study in Local Optimization (2008) (804)
Crossing Number is NP-Complete (1983) (745)
How easy is local search? (1985) (726)
An Application of Bin-Packing to Multiprocessor Scheduling (1978) (697)
A Catalog of Complexity Classes (1991) (675)
`` Strong '' NP-Completeness Results: Motivation, Examples, and Implications (1978) (669)
The NP-Completeness Column: An Ongoing Guide (1982) (668)
Near-optimal bin packing algorithms (1973) (656)
The Complexity of Multiterminal Cuts (1994) (653)
Some simplified NP-complete problems (1974) (635)
The Complexity of Computing Steiner Minimal Trees (1977) (577)
Fast Algorithms for Bin Packing (1974) (540)
The Planar Hamiltonian Circuit Problem is NP-Complete (1976) (532)
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms (1980) (517)
Complexity Results for Multiprocessor Scheduling under Resource Constraints (1975) (513)
The NP-Completeness Column: An Ongoing Guide (1986) (477)
Approximation Algorithms for Bin-Packing — An Updated Survey (1984) (468)
Local Optimization and the Traveling Salesman Problem (1990) (430)
The Complexity of Coloring Circular Arcs and Chords (1980) (425)
Cliques, Coloring, and Satisfiability (1996) (405)
The complexity of the network design problem (1978) (404)
The complexity of searching a graph (1981) (396)
Testing containment of conjunctive queries under functional and inclusion dependencies (1982) (395)
Some NP-complete geometric problems (1976) (387)
Resource Constrained Scheduling as Generalized Bin Packing (1976) (340)
A theoretician's guide to the experimental analysis of algorithms (1999) (336)
Triangulating a Simple Polygon (1978) (314)
The Complexity of Near-Optimal Graph Coloring (1976) (299)
The prize collecting Steiner tree problem: theory and practice (2000) (283)
COMPLEXITY RESULTS FOR BANDWIDTH MINIMIZATION (1978) (275)
Two-Processor Scheduling with Start-Times and Deadlines (1977) (245)
Computers and Inrracrobiliry: A Guide ro the Theory of NP-Completeness (1979) (237)
The complexity of multiway cuts (extended abstract) (1992) (233)
On Packing Two-Dimensional Bins (1982) (231)
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines (1981) (209)
Experimental Analysis of Heuristics for the STSP (2007) (203)
Scheduling File Transfers (1985) (182)
The computational complexity of inferring rooted phylogenies by parsimony (1986) (180)
Asymptotic experimental analysis for the Held-Karp traveling salesman bound (1996) (176)
On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees (1983) (173)
The Densest Hemisphere Problem (1978) (170)
An application of graph coloring to printed circuit testing (1975) (168)
On a Dual Version of the One-Dimensional Bin Packing Problem (1984) (164)
Dynamic Bin Packing (1983) (161)
Performance Guarantees for Scheduling Algorithms (1978) (153)
Dimacs series in discrete mathematics and theoretical computer science (1996) (149)
The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests (2001) (148)
The Rectilinear Steiner Problem is NP-Complete (1977) (145)
Scheduling Tasks with Nonuniform Deadlines on Two Processors (1976) (144)
Network Flows and Matching: First DIMACS Implementation Challenge (1993) (123)
Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness (1977) (122)
Approximation Algorithms for Bin Packing Problems: A Survey (1981) (116)
Data structures for traveling salesmen (1993) (115)
A 71/60 theorem for bin packing (1985) (106)
Bin packing with divisible item sizes (1987) (104)
Stockmeyer: some simplified np-complete graph problems (1976) (103)
Hypergraph planarity and the complexity of drawing venn diagrams (1987) (95)
Compressing Large Boolean Matrices using Reordering Techniques (2004) (87)
Scheduling Opposing Forests (1983) (84)
Bounded Space On-Line Bin Packing: Best Is Better than First (1991) (81)
Compressing rectilinear pictures and minimizing access control lists (2007) (79)
The NP-completeness column (2005) (74)
Some unexpected expected behavior results for bin packing (1984) (71)
The complexity of checkers on an N × N board (1978) (66)
8. The traveling salesman problem: a case study (2003) (60)
Bin Packing (2008) (58)
Better approximation algorithms for bin covering (2001) (58)
Approximation algorithms for combinatorial problems: an annotated bibliography (1976) (57)
On the Sum-of-Squares algorithm for bin packing (2002) (57)
The geometric maximum traveling salesman problem (2002) (54)
An application of Iterated Local Search to Graph Coloring (2002) (54)
Near-optimal intraprocedural branch alignment (1997) (53)
Generalized Planar Matching (1990) (53)
The Maximum Traveling Salesman Problem Under Polyhedral Norms (1998) (52)
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (2007) (52)
Optimizing Conjunctive Queries that Contain Untyped Variables (1983) (49)
Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, Proceedings of a DIMACS Workshop, USA, 1999 (2002) (49)
Simulation results of the capacity of cellular systems (1997) (48)
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings (2000) (47)
Markov chains, computer proofs, and average-case analysis of best fit bin packing (1993) (46)
The complexity of the network design problem : (preprint) (1977) (45)
Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study (1991) (43)
What are the least tractable instances of max independent set? (1999) (43)
A transformation for 2-D linear systems and a generalization of a theorem of Rosenbrock (1998) (42)
Proceedings of the twenty-first annual ACM symposium on Theory of computing (1989) (41)
Scheduling file transfers in a distributed network (1983) (39)
A Self Organizing Bin Packing Heuristic (1999) (39)
Bin packing with discrete item sizes, part II: Tight bounds on First Fit (1997) (29)
Fast Allocation Algorithms (1972) (29)
Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing (2002) (28)
Proceedings of the fifteenth annual ACM symposium on Theory of computing (1983) (27)
Foreword xiIntroduction to the Second DIMACS Challenge: Cliques, coloring, and satisfiability (1996) (26)
vLOD: high-fidelity walkthrough of large virtual environments (2005) (26)
Some simplified polynomial complete problems (1974) (24)
Representing Boolean Functions with If-Then-Else DAGs (1988) (23)
On the sum-of-squares algorithm for bin packing (2000) (23)
The NP-completeness column: Finding needles in haystacks (2007) (22)
Worst case bounds for simple one-dimensional packing algorithms (1974) (22)
The Cutting-Stock Approach to Bin Packing: Theory and Experiments (2003) (22)
Two Results Concerning Multicoloring (1978) (20)
The Complexity of Searching a Graph (Preliminary Version) (1981) (19)
A Brief History of NP-Completeness, 1954-2012 (2012) (18)
Special issue on computational methods for graph coloring and its generalizations (2008) (16)
Probabilistic Analysis of Packing and Related Partitioning Problems (1993) (15)
The genealogy of theoretical computer science: a preliminary report (1984) (14)
Disjoint-Path Facility Location: Theory and Practice (2011) (14)
Efficient and robust streaming provisioning in VPNs (2003) (13)
A POLYNOMIAL MATRIX THEORY FOR A CERTAIN CLASS OF TWO-DIMENSIONAL LINEAR SYSTEMS (1996) (13)
Emerging opportunities for theoretical computer science (1997) (13)
The NP-completeness column: The many limits on approximation (2006) (10)
How Easy Is Local Search? (Extended Abstract) (1985) (10)
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 (2007) (9)
Restrictions of Minimum Spanner Problems (1997) (9)
On Strongly Connected Digraphs with Bounded Cycle Length (1996) (8)
Voting power and target-based site prioritization. (2010) (7)
Combinatorial Optimization: Algorithms and Complexity. By Christos H. Papadimitriou and Kenneth Steiglitz (1984) (6)
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California, USA (1990) (6)
Data structures, near neibor searches, and methodology : fifth and sixth DIMACS implementation challenges : papers related to the DIMACS challenge on dictionaries and priority queues (1995-1996) and the DIMACS challenge on near neighbor searches (1998-1999) (2002) (6)
2 APPROXIMATION ALGORITHMS FOR BIN PACKING : A SURVEY (2014) (6)
On conditions guaranteeing two polynomial matrices possess identical zero structures (1992) (6)
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing (2005) (5)
On property Br (1976) (4)
Wireless coverage prediction via parametric shortest paths (2018) (3)
The Traveling Salesman Problem: A report on the State of the Art (1994) (3)
Min-Sum Bin Packing (2018) (3)
Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units (1977) (3)
Minimizing channel density by lateral shifting of components (1994) (3)
Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs (2016) (3)
Vector Bin Packing (2016) (2)
A note on "A note on 'Some simplified NP-complete graph problems'" (1978) (2)
2-D System Structure and Applications (1992) (2)
A stoc/focs bibliography: the last progress report (1990) (2)
Optimizing conjunctive queries when attribute domains are not disjoint (1981) (1)
A note on bisecting minimum spanning trees (1978) (1)
Composing Functions to Minimize Image Size (1985) (1)
LTCC Course on Graph Theory 2013 / 14 Notes 3 Complexity and Algorithms (2013) (0)
Chapter 34 ( II ) On NP-completeness (0)
5. Concluding Remarks (1975) (0)
Selected papers from the fourth annual ACM SIAM symposium on Discrete algorithms (1995) (0)
Polynomial Time Algorithms for Maximization Problems in Spaces with Polyhedral Norms (1998) (0)
10261 Abstracts Collection - Algorithm Engineering (2010) (0)
10261 Abstracts Collection Algorithm Engineering Dagstuhl Seminar (2010) (0)
Abstract of Talk: Graph Coloring Algorithm: Between a Rock and a Hard Place? (1978) (0)
How to do experiments (extended advertisement) (1996) (0)
selected papers from the third annual ACM-SIAM symposium on Discrete algorithms (1994) (0)
The Travelling Salesman Problem (Dagstuhl Seminar 02261) (2021) (0)
Running time vs. tour quality for the traveling salesman problem (1994) (0)
Proceedings of the 1998 Symposium on Integer Programming and Combinatorial Optimization The Maximum Traveling Salesman Problemunder Polyhedral (1998) (0)
A Brief History of SIGACT News and its Editors (1996) (0)
Discrete algorithms and complexity : proceedings of the Japan-US Joint Seminar, June 4-6, 1986, Kyoto, Japan (1987) (0)
Algorithm Engineering (Dagstuhl Seminar 13391) (2013) (0)
10261 Executive Summary - Algorithm Engineering (2010) (0)
STOC/FOCS bibliography (preliminary version) (1991) (0)
Vector Bin Packing. (2016) (0)
Min-Sum Bin Packing (2018) (0)
Data Structures for Traveling Salesmen (Abstract) (1990) (0)
Designing Multi-Commodity Flow Trees (1994) (0)
Generation of Digit Reversed Address Sequences for Fast Fourier Transforms (1991) (0)
In Exaclty One Triple of T. from a Steiner Triple System We Derive a Graph the Cardinality of a Minimum Cover for a Steiner Triple System Deened On (1994) (0)
Approximating The Minimum Equivalent Digraph (1995) (0)
Test Number of Wirelength Gain Problem Elements Test Number of Channel Width Gain Problem Elements Cij C 2 (0)
Symbolic calculation of greatest common divisor of 2D polynomial matrices (1995) (0)
Mathematics for Operations Research (2003) (0)
7 Packing Dynamically Changing Trees 6 Approximating an Optimal Compact Packing (2007) (0)
In a Distributed Algorithm for Minimum Spanning Tree, Acm Transactions on Programming Languages and Systems (1997) (0)
Proceedings of the Japan-US joint seminar on discrete algorithms and complexity (1987) (0)
What is the science in experimental computer science? (2007) (0)

This paper list is powered by the following services:

Other Resources About David S. Johnson

en.wikipedia.org

What Schools Are Affiliated With David S. Johnson?

David S. Johnson is affiliated with the following schools: