| 2008 |
|---|
| 110 | EE | David S. Johnson:
Bin Packing.
Encyclopedia of Algorithms 2008 |
| 109 | EE | Camil Demetrescu,
Andrew V. Goldberg,
David S. Johnson:
Implementation Challenge for Shortest Paths.
Encyclopedia of Algorithms 2008 |
| 108 | EE | David S. Johnson,
Anuj Mehrotra,
Michael A. Trick:
Special issue on computational methods for graph coloring and its generalizations.
Discrete Applied Mathematics 156(2): 145-146 (2008) |
| 2007 |
|---|
| 107 | | David S. Johnson,
Uriel Feige:
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007
ACM 2007 |
| 106 | EE | David S. Johnson:
What is the science in experimental computer science?
Experimental Computer Science 2007: 1 |
| 105 | EE | David Applegate,
Gruia Calinescu,
David S. Johnson,
Howard J. Karloff,
Katrina Ligett,
Jia Wang:
Compressing rectilinear pictures and minimizing access control lists.
SODA 2007: 1066-1075 |
| 104 | EE | David S. Johnson:
The NP-completeness column: Finding needles in haystacks.
ACM Transactions on Algorithms 3(2): (2007) |
| 2006 |
|---|
| 103 | EE | David S. Johnson:
The NP-completeness column: The many limits on approximation.
ACM Transactions on Algorithms 2(3): 473-489 (2006) |
| 102 | EE | János Csirik,
David S. Johnson,
Claire Kenyon,
James B. Orlin,
Peter W. Shor,
Richard R. Weber:
On the Sum-of-Squares algorithm for bin packing.
J. ACM 53(1): 1-65 (2006) |
| 2005 |
|---|
| 101 | EE | David S. Johnson:
The NP-completeness column.
ACM Transactions on Algorithms 1(1): 160-176 (2005) |
| 100 | EE | János Csirik,
David S. Johnson,
Claire Kenyon:
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing
CoRR abs/cs/0509031: (2005) |
| 99 | EE | Jatin Chhugani,
Budirijanto Purnomo,
Shankar Krishnan,
Jonathan D. Cohen,
Suresh Venkatasubramanian,
David S. Johnson,
Subodh Kumar:
vLOD: High-Fidelity Walkthrough of Large Virtual Environments.
IEEE Trans. Vis. Comput. Graph. 11(1): 35-47 (2005) |
| 2004 |
|---|
| 98 | EE | David S. Johnson,
Shankar Krishnan,
Jatin Chhugani,
Subodh Kumar,
Suresh Venkatasubramanian:
Compressing Large Boolean Matrices using Reordering Techniques.
VLDB 2004: 13-23 |
| 2003 |
|---|
| 97 | | David Applegate,
Luciana S. Buriol,
Bernard L. Dillard,
David S. Johnson,
Peter W. Shor:
The Cutting-Stock Approach to Bin Packing: Theory and Experiments.
ALENEX 2003: 1-15 |
| 96 | EE | Alexander I. Barvinok,
Sándor P. Fekete,
David S. Johnson,
Arie Tamir,
Gerhard J. Woeginger,
Russell Woodroofe:
The geometric maximum traveling salesman problem.
J. ACM 50(5): 641-664 (2003) |
| 2002 |
|---|
| 95 | EE | Alexander I. Barvinok,
Sándor P. Fekete,
David S. Johnson,
Arie Tamir,
Gerhard J. Woeginger,
Russell Woodroofe:
The Geometric Maximum Traveling Salesman Problem
CoRR cs.DS/0204024: (2002) |
| 94 | EE | János Csirik,
David S. Johnson,
Claire Kenyon,
James B. Orlin,
Peter W. Shor,
Richard R. Weber:
On the Sum-of-Squares Algorithm for Bin Packing
CoRR cs.DS/0210013: (2002) |
| 2001 |
|---|
| 93 | EE | Jill Cirasella,
David S. Johnson,
Lyle A. McGeoch,
Weixiong Zhang:
The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests.
ALENEX 2001: 32-59 |
| 92 | EE | János Csirik,
David S. Johnson,
Claire Kenyon:
Better approximation algorithms for bin covering.
SODA 2001: 557-566 |
| 91 | EE | János Csirik,
David S. Johnson:
Bounded Space On-Line Bin Packing: Best Is Better than First.
Algorithmica 31(2): 115-138 (2001) |
| 2000 |
|---|
| 90 | EE | David S. Johnson,
Maria Minkoff,
Steven Phillips:
The prize collecting Steiner tree problem: theory and practice.
SODA 2000: 760-769 |
| 89 | EE | János Csirik,
David S. Johnson,
Claire Kenyon,
James B. Orlin,
Peter W. Shor,
Richard R. Weber:
On the sum-of-squares algorithm for bin packing.
STOC 2000: 208-217 |
| 88 | EE | Edward G. Coffman Jr.,
Costas Courcoubetis,
M. R. Garey,
David S. Johnson,
Peter W. Shor,
Richard R. Weber,
Mihalis Yannakakis:
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.
SIAM J. Discrete Math. 13(3): 384-402 (2000) |
| 1999 |
|---|
| 87 | EE | János Csirik,
David S. Johnson,
Claire Kenyon,
Peter W. Shor,
Richard R. Weber:
A Self Organizing Bin Packing Heuristic.
ALENEX 1999: 246-265 |
| 86 | EE | David S. Johnson,
Mario Szegedy:
What are the Least Tractable Instances of max Tndependent Set?
SODA 1999: 927-928 |
| 1998 |
|---|
| 85 | EE | Alexander I. Barvinok,
David S. Johnson,
Gerhard J. Woeginger,
Russell Woodroofe:
The Maximum Traveling Salesman Problem Under Polyhedral Norms.
IPCO 1998: 195-201 |
| 1997 |
|---|
| 84 | | Cliff Young,
David S. Johnson,
David R. Karger,
Michael D. Smith:
Near-optimal Intraprocedural Branch Alignment.
PLDI 1997: 183-193 |
| 83 | | Edward G. Coffman Jr.,
David S. Johnson,
Peter W. Shor,
Richard R. Weber:
Bin packing with discrete item sizes, part II: Tight bounds on First Fit.
Random Struct. Algorithms 10(1-2): 69-101 (1997) |
| 1996 |
|---|
| 82 | | David S. Johnson,
Lyle A. McGeoch,
Edward E. Rothberg:
Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound.
SODA 1996: 341-350 |
| 1995 |
|---|
| 81 | | Michael L. Fredman,
David S. Johnson,
Lyle A. McGeoch,
G. Ostheimer:
Data Structures for Traveling Salesmen.
J. Algorithms 18(3): 432-479 (1995) |
| 1994 |
|---|
| 80 | | David S. Johnson:
The Traveling Salesman Problem: A report on the State of the Art.
IFIP Congress (1) 1994: 221-222 |
| 79 | | David S. Johnson,
Andrea S. LaPaugh,
Ron Y. Pinter:
Minimizing Channel Density by Lateral Shifting of Components.
SODA 1994: 122-131 |
| 78 | | Elias Dahlhaus,
David S. Johnson,
Christos H. Papadimitriou,
Paul D. Seymour,
Mihalis Yannakakis:
The Complexity of Multiterminal Cuts.
SIAM J. Comput. 23(4): 864-894 (1994) |
| 1993 |
|---|
| 77 | | Michael L. Fredman,
David S. Johnson,
Lyle A. McGeoch,
G. Ostheimer:
Data Structures for Traveling Salesmen.
SODA 1993: 145-154 |
| 76 | EE | Edward G. Coffman Jr.,
David S. Johnson,
Peter W. Shor,
Richard R. Weber:
Markov chains, computer proofs, and average-case analysis of best fit bin packing.
STOC 1993: 412-421 |
| 75 | | David S. Johnson,
Francine Berman:
Performance of the Efficient Data-Driven Evaluation Scheme.
J. Parallel Distrib. Comput. 18(3): 340-346 (1993) |
| 1992 |
|---|
| 74 | | Elias Dahlhaus,
David S. Johnson,
Christos H. Papadimitriou,
Paul D. Seymour,
Mihalis Yannakakis:
The Complexity of Multiway Cuts (Extended Abstract)
STOC 1992: 241-251 |
| 73 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 13(3): 502-524 (1992) |
| 1991 |
|---|
| 72 | | János Csirik,
David S. Johnson:
Bounded Space On-Line Bin Packing: Best is Better than First.
SODA 1991: 309-319 |
| 71 | | Edward G. Coffman Jr.,
Costas Courcoubetis,
M. R. Garey,
David S. Johnson,
Lyle A. McGeoch,
Peter W. Shor,
Richard R. Weber,
Mihalis Yannakakis:
Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
STOC 1991: 230-240 |
| 1990 |
|---|
| 70 | | David S. Johnson:
Local Optimization and the Traveling Salesman Problem.
ICALP 1990: 446-461 |
| 69 | | David S. Johnson:
Data Structures for Traveling Salesmen (Abstract).
SWAT 1990: 287 |
| 68 | | David S. Johnson:
A Catalog of Complexity Classes.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 67-161 |
| 67 | EE | Brent N. Clark,
Charles J. Colbourn,
David S. Johnson:
Unit disk graphs.
Discrete Mathematics 86(1-3): 165-177 (1990) |
| 66 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 11(1): 144-151 (1990) |
| 65 | | Francine Berman,
David S. Johnson,
Frank Thomson Leighton,
Peter W. Shor,
Larry Snyder:
Generalized Planar Matching.
J. Algorithms 11(2): 153-184 (1990) |
| 1988 |
|---|
| 64 | | David S. Johnson,
Christos H. Papadimitriou,
Mihalis Yannakakis:
On Generating All Maximal Independent Sets.
Inf. Process. Lett. 27(3): 119-123 (1988) |
| 63 | EE | Nimrod Megiddo,
S. Louis Hakimi,
M. R. Garey,
David S. Johnson,
Christos H. Papadimitriou:
The complexity of searching a graph.
J. ACM 35(1): 18-44 (1988) |
| 62 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 9(3): 426-444 (1988) |
| 61 | | David S. Johnson,
Christos H. Papadimitriou,
Mihalis Yannakakis:
How Easy is Local Search?
J. Comput. Syst. Sci. 37(1): 79-100 (1988) |
| 1987 |
|---|
| 60 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 8(2): 285-303 (1987) |
| 59 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 8(3): 438-448 (1987) |
| 58 | EE | Edward G. Coffman Jr.,
M. R. Garey,
David S. Johnson:
Bin packing with divisible item sizes.
J. Complexity 3(4): 406-428 (1987) |
| 1986 |
|---|
| 57 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 7(2): 289-305 (1986) |
| 56 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 7(4): 584-601 (1986) |
| 1985 |
|---|
| 55 | | David S. Johnson,
Christos H. Papadimitriou,
Mihalis Yannakakis:
How Easy Is Local Search? (Extended Abstract)
FOCS 1985: 39-42 |
| 54 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 6(1): 145-159 (1985) |
| 53 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 6(2): 291-305 (1985) |
| 52 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 6(3): 434-451 (1985) |
| 51 | EE | David S. Johnson,
M. R. Garey:
A 71/60 theorem for bin packing.
J. Complexity 1(1): 65-106 (1985) |
| 50 | | M. R. Garey,
David S. Johnson:
Composing Functions to Minimize Image Size.
SIAM J. Comput. 14(2): 500-503 (1985) |
| 49 | | Edward G. Coffman Jr.,
M. R. Garey,
David S. Johnson,
Andrea S. LaPaugh:
Scheduling File Transfers.
SIAM J. Comput. 14(4): 743-780 (1985) |
| 1984 |
|---|
| 48 | | Jon Louis Bentley,
David S. Johnson,
Frank Thomson Leighton,
Catherine C. McGeoch,
Lyle A. McGeoch:
Some Unexpected Expected Behavior Results for Bin Packing
STOC 1984: 279-288 |
| 47 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 5(1): 147-160 (1984) |
| 46 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 5(2): 284-299 (1984) |
| 45 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 5(3): 433-447 (1984) |
| 44 | | S. F. Assmann,
David S. Johnson,
Daniel J. Kleitman,
Joseph Y.-T. Leung:
On a Dual Version of the One-Dimensional Bin Packing Problem.
J. Algorithms 5(4): 502-525 (1984) |
| 43 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 5(4): 595-609 (1984) |
| 42 | | David S. Johnson,
Anthony C. Klug:
Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies.
J. Comput. Syst. Sci. 28(1): 167-189 (1984) |
| 1983 |
|---|
| 41 | | Edward G. Coffman Jr.,
M. R. Garey,
David S. Johnson,
Andrea S. LaPaugh:
Scheduling File Transfers in a Distributed Network.
PODC 1983: 254-266 |
| 40 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 4(1): 87-100 (1983) |
| 39 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 4(2): 189-203 (1983) |
| 38 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 4(3): 286-300 (1983) |
| 37 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 4(4): 397-411 (1983) |
| 36 | | Edward G. Coffman Jr.,
M. R. Garey,
David S. Johnson:
Dynamic Bin Packing.
SIAM J. Comput. 12(2): 227-258 (1983) |
| 35 | | David S. Johnson,
Anthony C. Klug:
Optimizing Conjunctive Queries that Contain Untyped Variables.
SIAM J. Comput. 12(4): 616-640 (1983) |
| 1982 |
|---|
| 34 | EE | David S. Johnson,
Anthony C. Klug:
Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies.
PODS 1982: 164-169 |
| 33 | | M. R. Garey,
David S. Johnson,
Hans S. Witsenhausen:
The complexity of the generalized Lloyd - Max problem.
IEEE Transactions on Information Theory 28(2): 255- (1982) |
| 32 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 3(1): 89-99 (1982) |
| 31 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 3(2): 182-195 (1982) |
| 30 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 3(3): 288-300 (1982) |
| 29 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 3(4): 381-395 (1982) |
| 1981 |
|---|
| 28 | | David S. Johnson,
Anthony C. Klug:
Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract)
FOCS 1981: 203-211 |
| 27 | | Nimrod Megiddo,
S. Louis Hakimi,
M. R. Garey,
David S. Johnson,
Christos H. Papadimitriou:
The Complexity of Searching a Graph (Preliminary Version)
FOCS 1981: 376-385 |
| 26 | | David S. Johnson:
The NP-Completeness Column: An Ongoing Guide.
J. Algorithms 2(4): 393-405 (1981) |
| 25 | | M. R. Garey,
David S. Johnson,
Barbara B. Simons,
Robert Endre Tarjan:
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.
SIAM J. Comput. 10(2): 256-269 (1981) |
| 1980 |
|---|
| 24 | | Edward G. Coffman Jr.,
M. R. Garey,
David S. Johnson,
Robert Endre Tarjan:
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.
SIAM J. Comput. 9(4): 808-826 (1980) |
| 1979 |
|---|
| 23 | | M. R. Garey,
David S. Johnson:
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman 1979 |
| 1978 |
|---|
| 22 | | Aviezri S. Fraenkel,
M. R. Garey,
David S. Johnson,
T. Schaefer,
Yaacov Yesha:
The Complexity of Checkers on an N * N Board - Preliminary Report
FOCS 1978: 55-64 |
| 21 | | M. R. Garey,
David S. Johnson,
Franco P. Preparata,
Robert Endre Tarjan:
Triangulating a Simple Polygon.
Inf. Process. Lett. 7(4): 175-179 (1978) |
| 20 | EE | M. R. Garey,
David S. Johnson:
``Strong'' NP-Completeness Results: Motivation, Examples, and Implications.
J. ACM 25(3): 499-508 (1978) |
| 19 | | Edward G. Coffman Jr.,
M. R. Garey,
David S. Johnson:
An Application of Bin-Packing to Multiprocessor Scheduling.
SIAM J. Comput. 7(1): 1-17 (1978) |
| 18 | | David S. Johnson,
Franco P. Preparata:
The Densest Hemisphere Problem.
Theor. Comput. Sci. 6: 93-107 (1978) |
| 1977 |
|---|
| 17 | | M. R. Garey,
Frank K. Hwang,
David S. Johnson:
Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units.
IEEE Trans. Computers 26(4): 321-328 (1977) |
| 16 | | M. R. Garey,
David S. Johnson:
Two-Processor Scheduling with Start-Times and Deadlines.
SIAM J. Comput. 6(3): 416-426 (1977) |
| 15 | | M. R. Garey,
David S. Johnson:
The Rectilinear Steiner Tree Problem in NP Complete.
SIAM Journal of Applied Mathematics 32: 826-834 (1977) |
| 1976 |
|---|
| 14 | | M. R. Garey,
Ronald L. Graham,
David S. Johnson:
Some NP-Complete Geometric Problems
STOC 1976: 10-22 |
| 13 | EE | M. R. Garey,
David S. Johnson:
The Complexity of Near-Optimal Graph Coloring.
J. ACM 23(1): 43-49 (1976) |
| 12 | EE | M. R. Garey,
David S. Johnson:
Scheduling Tasks with Nonuniform Deadlines on Two Processors.
J. ACM 23(3): 461-467 (1976) |
| 11 | | M. R. Garey,
Ronald L. Graham,
David S. Johnson:
Resource Constrained Scheduling as Generalized Bin Packing.
J. Comb. Theory, Ser. A 21(3): 257-298 (1976) |
| 10 | | M. R. Garey,
David S. Johnson,
Robert Endre Tarjan:
The Planar Hamiltonian Circuit Problem is NP-Complete.
SIAM J. Comput. 5(4): 704-714 (1976) |
| 9 | | M. R. Garey,
David S. Johnson,
Larry J. Stockmeyer:
Some Simplified NP-Complete Graph Problems.
Theor. Comput. Sci. 1(3): 237-267 (1976) |
| 1975 |
|---|
| 8 | | M. R. Garey,
David S. Johnson,
H. C. So:
An Application of Graph Coloring to Printed Circuit Testing (Working Paper)
FOCS 1975: 178-183 |
| 7 | | M. R. Garey,
David S. Johnson:
Complexity Results for Multiprocessor Scheduling under Resource Constraints.
SIAM J. Comput. 4(4): 397-411 (1975) |
| 1974 |
|---|
| 6 | | M. R. Garey,
David S. Johnson,
Larry J. Stockmeyer:
Some Simplified NP-Complete Problems
STOC 1974: 47-63 |
| 5 | | David S. Johnson:
Fast Algorithms for Bin Packing.
J. Comput. Syst. Sci. 8(3): 272-314 (1974) |
| 4 | | David S. Johnson:
Approximation Algorithms for Combinatorial Problems.
J. Comput. Syst. Sci. 9(3): 256-278 (1974) |
| 3 | | David S. Johnson,
Alan J. Demers,
Jeffrey D. Ullman,
M. R. Garey,
Ronald L. Graham:
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms.
SIAM J. Comput. 3(4): 299-325 (1974) |
| 1973 |
|---|
| 2 | | David S. Johnson:
Approximation Algorithms for Combinatorial Problems
STOC 1973: 38-49 |
| 1972 |
|---|
| 1 | | David S. Johnson:
Fast Allocation Algorithms
FOCS 1972: 144-154 |
