dblp.uni-trier.dewww.uni-trier.de

David S. Johnson

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2008
110EEDavid S. Johnson: Bin Packing. Encyclopedia of Algorithms 2008
109EECamil Demetrescu, Andrew V. Goldberg, David S. Johnson: Implementation Challenge for Shortest Paths. Encyclopedia of Algorithms 2008
108EEDavid 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
106EEDavid S. Johnson: What is the science in experimental computer science? Experimental Computer Science 2007: 1
105EEDavid 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
104EEDavid S. Johnson: The NP-completeness column: Finding needles in haystacks. ACM Transactions on Algorithms 3(2): (2007)
2006
103EEDavid S. Johnson: The NP-completeness column: The many limits on approximation. ACM Transactions on Algorithms 2(3): 473-489 (2006)
102EEJá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
101EEDavid S. Johnson: The NP-completeness column. ACM Transactions on Algorithms 1(1): 160-176 (2005)
100EEJá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)
99EEJatin 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
98EEDavid 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
96EEAlexander 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
95EEAlexander 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)
94EEJá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
93EEJill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang: The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. ALENEX 2001: 32-59
92EEJános Csirik, David S. Johnson, Claire Kenyon: Better approximation algorithms for bin covering. SODA 2001: 557-566
91EEJános Csirik, David S. Johnson: Bounded Space On-Line Bin Packing: Best Is Better than First. Algorithmica 31(2): 115-138 (2001)
2000
90EEDavid S. Johnson, Maria Minkoff, Steven Phillips: The prize collecting Steiner tree problem: theory and practice. SODA 2000: 760-769
89EEJá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
88EEEdward 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
87EEJános Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber: A Self Organizing Bin Packing Heuristic. ALENEX 1999: 246-265
86EEDavid S. Johnson, Mario Szegedy: What are the Least Tractable Instances of max Tndependent Set? SODA 1999: 927-928
1998
85EEAlexander 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
76EEEdward 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
67EEBrent 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)
63EENimrod 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)
58EEEdward 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)
51EEDavid 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
34EEDavid 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)
20EEM. 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
13EEM. R. Garey, David S. Johnson: The Complexity of Near-Optimal Graph Coloring. J. ACM 23(1): 43-49 (1976)
12EEM. 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

Coauthor Index

1David Applegate [97] [105]
2S. F. Assmann [44]
3Alexander I. Barvinok [85] [95] [96]
4Jon Louis Bentley [48]
5Francine Berman (Fran Berman) [65] [75]
6Luciana S. Buriol [97]
7Gruia Calinescu [105]
8Jatin Chhugani [98] [99]
9Jill Cirasella [93]
10Brent N. Clark [67]
11Edward G. Coffman Jr. [19] [24] [36] [41] [49] [58] [71] [76] [83] [88]
12Jonathan D. Cohen [99]
13Charles J. Colbourn [67]
14Costas Courcoubetis [71] [88]
15János Csirik [72] [87] [89] [91] [92] [94] [100] [102]
16Elias Dahlhaus [74] [78]
17Alan J. Demers [3]
18Camil Demetrescu [109]
19Bernard L. Dillard [97]
20Uriel Feige [107]
21Sándor P. Fekete [95] [96]
22Aviezri S. Fraenkel [22]
23Michael L. Fredman [77] [81]
24M. R. Garey (Michael R. Garey) [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] [51] [58] [63] [71] [88]
25Andrew V. Goldberg [109]
26Ronald L. Graham [3] [11] [14]
27S. Louis Hakimi [27] [63]
28Frank K. Hwang (Frank Kwang-Ming Hwang) [17]
29David R. Karger [84]
30Howard J. Karloff [105]
31Daniel J. Kleitman [44]
32Anthony C. Klug [28] [34] [35] [42]
33Shankar Krishnan [98] [99]
34Subodh Kumar [98] [99]
35Andrea S. LaPaugh [41] [49] [79]
36Frank Thomson Leighton (Tom Leighton) [48] [65]
37Joseph Y.-T. Leung [44]
38Katrina Ligett [105]
39Claire Mathieu (Claire Kenyon, Claire Kenyon-Mathieu) [87] [89] [92] [94] [100] [102]
40Catherine C. McGeoch [48]
41Lyle A. McGeoch [48] [71] [77] [81] [82] [93]
42Nimrod Megiddo [27] [63]
43Anuj Mehrotra [108]
44Maria Minkoff [90]
45James B. Orlin [89] [94] [102]
46G. Ostheimer [77] [81]
47Christos H. Papadimitriou [27] [55] [61] [63] [64] [74] [78]
48Steven Phillips [90]
49Ron Y. Pinter [79]
50Franco P. Preparata [18] [21]
51Budirijanto Purnomo [99]
52Edward E. Rothberg [82]
53T. Schaefer [22]
54Paul D. Seymour [74] [78]
55Peter W. Shor [65] [71] [76] [83] [87] [88] [89] [94] [97] [102]
56Barbara B. Simons (Barbara Simons) [25]
57Michael D. Smith [84]
58Lawrence Snyder (Larry Snyder) [65]
59H. C. So [8]
60Larry J. Stockmeyer [6] [9]
61Mario Szegedy [86]
62Arie Tamir [95] [96]
63Robert Endre Tarjan [10] [21] [24] [25]
64Michael A. Trick [108]
65Jeffrey D. Ullman [3]
66Suresh Venkatasubramanian [98] [99]
67Jia Wang [105]
68Richard R. Weber [71] [76] [83] [87] [88] [89] [94] [102]
69Hans S. Witsenhausen [33]
70Gerhard J. Woeginger [85] [95] [96]
71Russell Woodroofe [85] [95] [96]
72Mihalis Yannakakis [55] [61] [64] [71] [74] [78] [88]
73Yaacov Yesha [22]
74Cliff Young [84]
75Weixiong Zhang [93]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)