| |
      |
                                          |
Note: Links lead to the DBLP on the Web. David S. Johnson Jatin Chhugani , Budirijanto Purnomo , Shankar Krishnan , Jonathan 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) David S. Johnson, Shankar Krishnan , Jatin Chhugani , Subodh Kumar , Suresh Venkatasubramanian : Compressing Large Boolean Matrices using Reordering Techniques. VLDB 2004 : 13-23 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 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) 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) 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) Jill Cirasella , David S. Johnson, Lyle A. McGeoch , Weixiong Zhang : The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. ALENEX 2001 : 32-59 János Csirik , David S. Johnson, Claire Kenyon : Better approximation algorithms for bin covering. SODA 2001 : 557-566 János Csirik , David S. Johnson: Bounded Space On-Line Bin Packing: Best Is Better than First. Algorithmica 31 (2): 115-138 (2001) David S. Johnson, Maria Minkoff , Steven Phillips : The prize collecting Steiner tree problem: theory and practice. SODA 2000 : 760-769 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 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) János Csirik , David S. Johnson, Claire Kenyon , Peter W. Shor , Richard R. Weber : A Self Organizing Bin Packing Heuristic. ALENEX 1999 : 246-265 David S. Johnson, Mario Szegedy : What are the Least Tractable Instances of max Tndependent Set? SODA 1999 : 927-928 Alexander I. Barvinok , David S. Johnson, Gerhard J. Woeginger , Russell Woodroofe : The Maximum Traveling Salesman Problem Under Polyhedral Norms. IPCO 1998 : 195-201 Cliff Young , David S. Johnson, David R. Karger , Michael D. Smith : Near-optimal Intraprocedural Branch Alignment. PLDI 1997 : 183-193 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) David S. Johnson, Lyle A. McGeoch , Edward E. Rothberg : Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. SODA 1996 : 341-350 Michael L. Fredman , David S. Johnson, Lyle A. McGeoch , G. Ostheimer : Data Structures for Traveling Salesmen. J. Algorithms 18 (3): 432-479 (1995) David S. Johnson: The Traveling Salesman Problem: A report on the State of the Art. IFIP Congress (1) 1994 : 221-222 David S. Johnson, Andrea S. LaPaugh , Ron Y. Pinter : Minimizing Channel Density by Lateral Shifting of Components. SODA 1994 : 122-131 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) Michael L. Fredman , David S. Johnson, Lyle A. McGeoch , G. Ostheimer : Data Structures for Traveling Salesmen. SODA 1993 : 145-154 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 David S. Johnson, Francine Berman : Performance of the Efficient Data-Driven Evaluation Scheme. J. Parallel Distrib. Comput. 18 (3): 340-346 (1993) Elias Dahlhaus , David S. Johnson, Christos H. Papadimitriou , Paul D. Seymour , Mihalis Yannakakis : The Complexity of Multiway Cuts (Extended Abstract) STOC 1992 : 241-251 David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 13 (3): 502-524 (1992) János Csirik , David S. Johnson: Bounded Space On-Line Bin Packing: Best is Better than First. SODA 1991 : 309-319 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 David S. Johnson: Local Optimization and the Traveling Salesman Problem. ICALP 1990 : 446-461 David S. Johnson: Data Structures for Traveling Salesmen (Abstract). SWAT 1990 : 287 David S. Johnson: A Catalog of Complexity Classes. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990 : 67-161 David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 11 (1): 144-151 (1990) Francine Berman , David S. Johnson, Frank Thomson Leighton , Peter W. Shor , Larry Snyder : Generalized Planar Matching. J. Algorithms 11 (2): 153-184 (1990) David S. Johnson, Christos H. Papadimitriou : On Generating All Maximal Independent Sets. Inf. Process. Lett. 27 (3): 119-123 (1988) 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) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 9 (3): 426-444 (1988) David S. Johnson, Christos H. Papadimitriou , Mihalis Yannakakis : How Easy is Local Search? J. Comput. Syst. Sci. 37 (1): 79-100 (1988) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 8 (2): 285-303 (1987) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 8 (3): 438-448 (1987) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 7 (2): 289-305 (1986) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 7 (4): 584-601 (1986) David S. Johnson, Christos H. Papadimitriou , Mihalis Yannakakis : How Easy Is Local Search? (Extended Abstract) FOCS 1985 : 39-42 David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6 (1): 145-159 (1985) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6 (2): 291-305 (1985) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6 (3): 434-451 (1985) M. R. Garey , David S. Johnson: Composing Functions to Minimize Image Size. SIAM J. Comput. 14 (2): 500-503 (1985) Edward G. Coffman Jr. , M. R. Garey , David S. Johnson, Andrea S. LaPaugh : Scheduling File Transfers. SIAM J. Comput. 14 (4): 743-780 (1985) 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 David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5 (1): 147-160 (1984) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5 (2): 284-299 (1984) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5 (3): 433-447 (1984) 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) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5 (4): 595-609 (1984) 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) Edward G. Coffman Jr. , M. R. Garey , David S. Johnson, Andrea S. LaPaugh : Scheduling File Transfers in a Distributed Network. PODC 1983 : 254-266 David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4 (1): 87-100 (1983) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4 (2): 189-203 (1983) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4 (3): 286-300 (1983) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4 (4): 397-411 (1983) Edward G. Coffman Jr. , M. R. Garey , David S. Johnson: Dynamic Bin Packing. SIAM J. Comput. 12 (2): 227-258 (1983) David S. Johnson, Anthony C. Klug : Optimizing Conjunctive Queries that Contain Untyped Variables. SIAM J. Comput. 12 (4): 616-640 (1983) David S. Johnson, Anthony C. Klug : Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982 : 164-169 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) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3 (1): 89-99 (1982) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3 (2): 182-195 (1982) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3 (3): 288-300 (1982) David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3 (4): 381-395 (1982) David S. Johnson, Anthony C. Klug : Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract) FOCS 1981 : 203-211 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 David S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 2 (4): 393-405 (1981) 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) 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) M. R. Garey , David S. Johnson: Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979 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 M. R. Garey , David S. Johnson, Franco P. Preparata , Robert Endre Tarjan : Triangulating a Simple Polygon. Inf. Process. Lett. 7 (4): 175-179 (1978) M. R. Garey , David S. Johnson: ``Strong'' NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25 (3): 499-508 (1978) 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) David S. Johnson, Franco P. Preparata : The Densest Hemisphere Problem. Theor. Comput. Sci. 6 : 93-107 (1978) 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) M. R. Garey , David S. Johnson: Two-Processor Scheduling with Start-Times and Deadlines. SIAM J. Comput. 6 (3): 416-426 (1977) M. R. Garey , David S. Johnson: The Rectilinear Steiner Tree Problem in NP Complete. SIAM Journal of Applied Mathematics 32 : 826-834 (1977) M. R. Garey , Ronald L. Graham , David S. Johnson: Some NP-Complete Geometric Problems STOC 1976 : 10-22 M. R. Garey , David S. Johnson: The Complexity of Near-Optimal Graph Coloring. J. ACM 23 (1): 43-49 (1976) M. R. Garey , David S. Johnson: Scheduling Tasks with Nonuniform Deadlines on Two Processors. J. ACM 23 (3): 461-467 (1976) 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) 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) M. R. Garey , David S. Johnson, Larry J. Stockmeyer : Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1 (3): 237-267 (1976) M. R. Garey , David S. Johnson, H. C. So : An Application of Graph Coloring to Printed Circuit Testing (Working Paper) FOCS 1975 : 178-183 M. R. Garey , David S. Johnson: Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM J. Comput. 4 (4): 397-411 (1975) M. R. Garey , David S. Johnson, Larry J. Stockmeyer : Some Simplified NP-Complete Problems STOC 1974 : 47-63 David S. Johnson: Fast Algorithms for Bin Packing. J. Comput. Syst. Sci. 8 (3): 272-314 (1974) David S. Johnson: Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. 9 (3): 256-278 (1974) 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) David S. Johnson: Approximation Algorithms for Combinatorial Problems STOC 1973 : 38-49 David S. Johnson: Fast Allocation Algorithms FOCS 1972 : 144-154 1 [ 94 ] 2 [ 44 ] 3 [ 82 ] [ 92 ] [ 93 ] 4 [ 48 ] 5 [ 63 ] [ 72 ] 6 [ 94 ] 7 [ 95 ] [ 96 ] 8 [ 90 ] 9 [ 19 ] [ 24 ] [ 36 ] [ 41 ] [ 49 ] [ 68 ] [ 73 ] [ 80 ] [ 85 ] 10 [ 96 ] 11 [ 68 ] [ 85 ] 12 [ 69 ] [ 84 ] [ 86 ] [ 88 ] [ 89 ] [ 91 ] 13 [ 71 ] [ 75 ] 14 [ 3 ] 15 [ 94 ] 16 [ 92 ] [ 93 ] 17 [ 22 ] 18 [ 74 ] [ 78 ] 19 [ 3 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 25 ] [ 27 ] [ 33 ] [ 36 ] [ 41 ] [ 49 ] [ 50 ] [ 61 ] [ 68 ] [ 85 ] 20 [ 3 ] [ 11 ] [ 14 ] 21 [ 27 ] [ 61 ] 22 [ 17 ] 23 [ 81 ] 24 [ 84 ] [ 86 ] [ 89 ] [ 91 ] 25 [ 44 ] 26 [ 28 ] [ 34 ] [ 35 ] [ 42 ] 27 [ 95 ] [ 96 ] 28 [ 95 ] [ 96 ] 29 [ 41 ] [ 49 ] [ 76 ] 30 [ 48 ] [ 63 ] 31 [ 44 ] 32 [ 48 ] 33 [ 48 ] [ 68 ] [ 74 ] [ 78 ] [ 79 ] [ 90 ] 34 [ 27 ] [ 61 ] 35 [ 87 ] 36 [ 86 ] [ 91 ] 37 [ 74 ] [ 78 ] 38 [ 27 ] [ 54 ] [ 59 ] [ 61 ] [ 62 ] [ 71 ] [ 75 ] 39 [ 87 ] 40 [ 76 ] 41 [ 18 ] [ 21 ] 42 [ 96 ] 43 [ 79 ] 44 [ 22 ] 45 [ 71 ] [ 75 ] 46 [ 63 ] [ 68 ] [ 73 ] [ 80 ] [ 84 ] [ 85 ] [ 86 ] [ 91 ] [ 94 ] 47 [ 25 ] 48 [ 81 ] 49 [ 63 ] 50 [ 8 ] 51 [ 6 ] [ 9 ] 52 [ 83 ] 53 [ 92 ] [ 93 ] 54 [ 10 ] [ 21 ] [ 24 ] [ 25 ] 55 [ 3 ] 56 [ 95 ] [ 96 ] 57 [ 68 ] [ 73 ] [ 80 ] [ 84 ] [ 85 ] [ 86 ] [ 91 ] 58 [ 33 ] 59 [ 82 ] [ 92 ] [ 93 ] 60 [ 82 ] [ 92 ] [ 93 ] 61 [ 54 ] [ 59 ] [ 68 ] [ 71 ] [ 75 ] [ 85 ] 62 [ 22 ] 63 [ 81 ] 64 [ 90 ]  ©2005 Association for Computing Machinery |
