David S. Johnson Home Page Coauthor index DBLP Vis pubzone.org

List of publications from the DBLP Bibliography Server - FAQ
Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

DBLP keys2008
115Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: Bin Packing. Encyclopedia of Algorithms 2008
114Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLCamil Demetrescu, Andrew V. Goldberg, David S. Johnson: Implementation Challenge for Shortest Paths. Encyclopedia of Algorithms 2008
113Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid 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
112no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid 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
111Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: What is the science in experimental computer science? Experimental Computer Science 2007: 1
110Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid 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
109Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-completeness column: Finding needles in haystacks. ACM Transactions on Algorithms 3(2): (2007)
2006
108Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-completeness column: The many limits on approximation. ACM Transactions on Algorithms 2(3): 473-489 (2006)
107Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJá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
106Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-completeness column. ACM Transactions on Algorithms 1(1): 160-176 (2005)
105Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJá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)
104Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJatin 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
103Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Shankar Krishnan, Jatin Chhugani, Subodh Kumar, Suresh Venkatasubramanian: Compressing Large Boolean Matrices using Reordering Techniques. VLDB 2004: 13-23
2003
102no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid 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
101Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAlexander 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
100Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAlexander 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)
99Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJá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
98Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang: The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. ALENEX 2001: 32-59
97Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJános Csirik, David S. Johnson, Claire Kenyon: Better approximation algorithms for bin covering. SODA 2001: 557-566
96Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJános Csirik, David S. Johnson: Bounded Space On-Line Bin Packing: Best Is Better than First. Algorithmica 31(2): 115-138 (2001)
2000
95Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Maria Minkoff, Steven Phillips: The prize collecting Steiner tree problem: theory and practice. SODA 2000: 760-769
94Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJá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
93Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward 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
92Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJános Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber: A Self Organizing Bin Packing Heuristic. ALENEX 1999: 246-265
91Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Mario Szegedy: What are the Least Tractable Instances of max Tndependent Set? SODA 1999: 927-928
1998
90Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAlexander I. Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe: The Maximum Traveling Salesman Problem Under Polyhedral Norms. IPCO 1998: 195-201
1997
89Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLCliff Young, David S. Johnson, David R. Karger, Michael D. Smith: Near-optimal Intraprocedural Branch Alignment. PLDI 1997: 183-193
88no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward 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)
87Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAlfred V. Aho, David S. Johnson, Richard M. Karp, S. Rao Kosaraju, Catherine C. McGeoch, Christos H. Papadimitriou, Pavel A. Pevzner: Emerging opportunities for theoretical computer science. SIGACT News 28(3): 65-74 (1997)
86Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAnne 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: Strategic directions in research in theory of computing. SIGACT News 28(3): 75-93 (1997)
1996
85Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Lyle A. McGeoch, Edward E. Rothberg: Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. SODA 1996: 341-350
84Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: How to do experiments (extended advertisement). SIGACT News 27(2): 87 (1996)
83Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: A Brief History of SIGACT News and its Editors. SIGACT News 27(3): 125 (1996)
1995
82no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMichael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer: Data Structures for Traveling Salesmen. J. Algorithms 18(3): 432-479 (1995)
1994
81no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The Traveling Salesman Problem: A report on the State of the Art. IFIP Congress (1) 1994: 221-222
80Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Andrea S. LaPaugh, Ron Y. Pinter: Minimizing Channel Density by Lateral Shifting of Components. SODA 1994: 122-131
79no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias 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
78Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMichael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer: Data Structures for Traveling Salesmen. SODA 1993: 145-154
77Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward 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
76no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Francine Berman: Performance of the Efficient Data-Driven Evaluation Scheme. J. Parallel Distrib. Comput. 18(3): 340-346 (1993)
1992
75no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis: The Complexity of Multiway Cuts (Extended Abstract) STOC 1992: 241-251
74no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 13(3): 502-524 (1992)
1991
73Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJános Csirik, David S. Johnson: Bounded Space On-Line Bin Packing: Best is Better than First. SODA 1991: 309-319
72no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward 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
71Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: Local Optimization and the Traveling Salesman Problem. ICALP 1990: 446-461
70Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: Data Structures for Traveling Salesmen (Abstract). SWAT 1990: 287
69no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: A Catalog of Complexity Classes. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 67-161
68Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLBrent N. Clark, Charles J. Colbourn, David S. Johnson: Unit disk graphs. Discrete Mathematics 86(1-3): 165-177 (1990)
67no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 11(1): 144-151 (1990)
66no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFrancine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder: Generalized Planar Matching. J. Algorithms 11(2): 153-184 (1990)
65Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: A stoc/focs bibliography: the last progress report. SIGACT News 21(2): 4 (1990)
1988
64no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: On Generating All Maximal Independent Sets. Inf. Process. Lett. 27(3): 119-123 (1988)
63Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNimrod 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)
62no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 9(3): 426-444 (1988)
61no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy is Local Search? J. Comput. Syst. Sci. 37(1): 79-100 (1988)
1987
60no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 8(2): 285-303 (1987)
59no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 8(3): 438-448 (1987)
58Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward G. Coffman Jr., M. R. Garey, David S. Johnson: Bin packing with divisible item sizes. J. Complexity 3(4): 406-428 (1987)
1986
57no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 7(2): 289-305 (1986)
56no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 7(4): 584-601 (1986)
1985
55no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: How Easy Is Local Search? (Extended Abstract) FOCS 1985: 39-42
54no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6(1): 145-159 (1985)
53no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6(2): 291-305 (1985)
52no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 6(3): 434-451 (1985)
51Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, M. R. Garey: A 71/60 theorem for bin packing. J. Complexity 1(1): 65-106 (1985)
50no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: Composing Functions to Minimize Image Size. SIAM J. Comput. 14(2): 500-503 (1985)
49no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh: Scheduling File Transfers. SIAM J. Comput. 14(4): 743-780 (1985)
1984
48no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJon 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
47no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(1): 147-160 (1984)
46no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(2): 284-299 (1984)
45no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(3): 433-447 (1984)
44no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLS. 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)
43no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 5(4): 595-609 (1984)
42no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid 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
41no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh: Scheduling File Transfers in a Distributed Network. PODC 1983: 254-266
40no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(1): 87-100 (1983)
39no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(2): 189-203 (1983)
38no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(3): 286-300 (1983)
37no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 4(4): 397-411 (1983)
36no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward G. Coffman Jr., M. R. Garey, David S. Johnson: Dynamic Bin Packing. SIAM J. Comput. 12(2): 227-258 (1983)
35no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries that Contain Untyped Variables. SIAM J. Comput. 12(4): 616-640 (1983)
1982
34Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169
33no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. 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)
32no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(1): 89-99 (1982)
31no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(2): 182-195 (1982)
30no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(3): 288-300 (1982)
29no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 3(4): 381-395 (1982)
1981
28no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract) FOCS 1981: 203-211
27no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNimrod 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
26no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: The NP-Completeness Column: An Ongoing Guide. J. Algorithms 2(4): 393-405 (1981)
25no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. 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
24no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward 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
23no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979
1978
22no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAviezri 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
21no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan: Triangulating a Simple Polygon. Inf. Process. Lett. 7(4): 175-179 (1978)
20Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: ``Strong'' NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25(3): 499-508 (1978)
19no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLEdward 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)
18no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson, Franco P. Preparata: The Densest Hemisphere Problem. Theor. Comput. Sci. 6: 93-107 (1978)
1977
17no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. 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)
16no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: Two-Processor Scheduling with Start-Times and Deadlines. SIAM J. Comput. 6(3): 416-426 (1977)
15no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: The Rectilinear Steiner Tree Problem in NP Complete. SIAM Journal of Applied Mathematics 32: 826-834 (1977)
1976
14no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, Ronald L. Graham, David S. Johnson: Some NP-Complete Geometric Problems STOC 1976: 10-22
13Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: The Complexity of Near-Optimal Graph Coloring. J. ACM 23(1): 43-49 (1976)
12Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: Scheduling Tasks with Nonuniform Deadlines on Two Processors. J. ACM 23(3): 461-467 (1976)
11no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. 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)
10no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson, Robert Endre Tarjan: The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput. 5(4): 704-714 (1976)
9no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267 (1976)
1975
8no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson, H. C. So: An Application of Graph Coloring to Printed Circuit Testing (Working Paper) FOCS 1975: 178-183
7no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson: Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM J. Comput. 4(4): 397-411 (1975)
1974
6no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLM. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Problems STOC 1974: 47-63
5no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: Fast Algorithms for Bin Packing. J. Comput. Syst. Sci. 8(3): 272-314 (1974)
4no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. 9(3): 256-278 (1974)
3no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid 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
2no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: Approximation Algorithms for Combinatorial Problems STOC 1973: 38-49
1972
1no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDavid S. Johnson: Fast Allocation Algorithms FOCS 1972: 144-154

Coauthor Index

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

Colors in the list of coauthors

Copyright © Mon Mar 15 21:39:48 2010 by Michael Ley (ley@uni-trier.de)