David S. Johnson

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