David S. Johnson

160 papers A* 31A 5B 3Misc 1Journal 97Unranked 11

Year	Rank	Type	Title / Venue / Authors
2020	J	`jnl`	Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs. Oper. Res. David S. Johnson, Lee Breslau, Ilias Diakonikolas, Nick Duffield, Yu Gu, MohammadTaghi Hajiaghayi, Howard J. Karloff, Mauricio G. C. Resende, Subhabrata Sen
2020	J	`jnl`	The combinatorics of hidden diversity. Theor. Comput. Sci. Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung
2018	J	`jnl`	Min-Sum Bin Packing. J. Comb. Optim. Leah Epstein, David S. Johnson, Asaf Levin
2018	B	`conf`	Wireless coverage prediction via parametric shortest paths. MobiHoc David L. Applegate, Aaron Archer, David S. Johnson, Evdokia Nikolova, Mikkel Thorup, Ger Yang
2018	J	`jnl`	Wireless coverage prediction via parametric shortest paths. CoRR David L. Applegate, Aaron Archer, David S. Johnson, Evdokia Nikolova, Mikkel Thorup, Ger Yang
2016	—	`ch.`	Bin Packing. Encyclopedia of Algorithms David S. Johnson
2016	—	`ch.`	Implementation Challenge for Shortest Paths. Encyclopedia of Algorithms Camil Demetrescu, Andrew V. Goldberg, David S. Johnson
2016	J	`jnl`	Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs. CoRR David S. Johnson, Lee Breslau, Ilias Diakonikolas, Nick G. Duffield, Yu Gu, MohammadTaghi Hajiaghayi, Howard J. Karloff, Mauricio G. C. Resende, Subhabrata Sen
2016	J	`jnl`	Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111). Dagstuhl Reports Daniel Delling, Camil Demetrescu, David S. Johnson, Jan Vitek
2016	—	`ch.`	Vector Bin Packing. Encyclopedia of Algorithms David S. Johnson
2015	—	`conf`	A Little Honesty Goes a Long Way - The Two-Tier Model for Secure Multiparty Computation. TCC (1) Juan A. Garay, Ran Gelles, David S. Johnson, Aggelos Kiayias, Moti Yung
2014	J	`jnl`	A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation. IACR Cryptol. ePrint Arch. Juan A. Garay, Ran Gelles, David S. Johnson, Aggelos Kiayias, Moti Yung
2013	J	`jnl`	Algorithm Engineering (Dagstuhl Seminar 13391). Dagstuhl Reports Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, Dorothea Wagner
2013	A	`conf`	Resource-based corruptions and the combinatorics of hidden diversity. ITCS Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung
2012	J	`jnl`	Resource-based Corruptions and the Combinatorics of Hidden Diversity. IACR Cryptol. ePrint Arch. Juan A. Garay, David S. Johnson, Aggelos Kiayias, Moti Yung
2011	A	`conf`	Disjoint-Path Facility Location: Theory and Practice. ALENEX Lee Breslau, Ilias Diakonikolas, Nick G. Duffield, Yu Gu, Mohammad Taghi Hajiaghayi, David S. Johnson, Howard J. Karloff, Mauricio G. C. Resende, Subhabrata Sen
2010	—	`conf`	10261 Abstracts Collection - Algorithm Engineering. Algorithm Engineering Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, Peter Sanders
2010	—	`conf`	10261 Executive Summary - Algorithm Engineering. Algorithm Engineering Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, Peter Sanders
2010	—	`ed.`	Algorithm Engineering, 27.06. - 02.07.2010 Algorithm Engineering Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, Peter Sanders
2009	—	`ed.`	The Shortest Path Problem, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 13-14, 2006 The Shortest Path Problem Camil Demetrescu, Andrew V. Goldberg, David S. Johnson
2008	—	`ch.`	Bin Packing. Encyclopedia of Algorithms David S. Johnson
2008	—	`ch.`	Implementation Challenge for Shortest Paths. Encyclopedia of Algorithms Camil Demetrescu, Andrew V. Goldberg, David S. Johnson
2008	J	`jnl`	Special issue on computational methods for graph coloring and its generalizations. Discret. Appl. Math. David S. Johnson, Anuj Mehrotra, Michael A. Trick
2007	A*	`conf`	Compressing rectilinear pictures and minimizing access control lists. SODA David L. Applegate, Gruia Calinescu, David S. Johnson, Howard J. Karloff, Katrina Ligett, Jia Wang
2007	A*	`ed.`	Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 STOC David S. Johnson, Uriel Feige
2007	J	`jnl`	The NP-completeness column: Finding needles in haystacks. ACM Trans. Algorithms David S. Johnson
2007	—	`conf`	What is the science in experimental computer science? Experimental Computer Science David S. Johnson
2006	J	`jnl`	On the Sum-of-Squares algorithm for bin packing. J. ACM János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
2006	J	`jnl`	The NP-completeness column: The many limits on approximation. ACM Trans. Algorithms David S. Johnson
2005	J	`jnl`	On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing CoRR János Csirik, David S. Johnson, Claire Kenyon
2005	J	`jnl`	The NP-completeness column. ACM Trans. Algorithms David S. Johnson
2005	J	`jnl`	vLOD: High-Fidelity Walkthrough of Large Virtual Environments. IEEE Trans. Vis. Comput. Graph. Jatin Chhugani, Budirijanto Purnomo, Shankar Krishnan, Jonathan D. Cohen, Suresh Venkatasubramanian, David S. Johnson, Subodh Kumar
2004	A*	`conf`	Compressing Large Boolean Matrices using Reordering Techniques. VLDB David S. Johnson, Shankar Krishnan, Jatin Chhugani, Subodh Kumar, Suresh Venkatasubramanian
2003	A	`conf`	The Cutting-Stock Approach to Bin Packing: Theory and Experiments. ALENEX David L. Applegate, Luciana S. Buriol, Bernard L. Dillard, David S. Johnson, Peter W. Shor
2003	J	`jnl`	The geometric maximum traveling salesman problem. J. ACM Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe
2002	—	`ed.`	Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, Proceedings of a DIMACS Workshop, USA, 1999 Data Structures, Near Neighbor Searches, and Methodology Michael H. Goldwasser, David S. Johnson, Catherine C. McGeoch
2002	J	`jnl`	On the Sum-of-Squares Algorithm for Bin Packing CoRR János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
2002	J	`jnl`	Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing. SIAM Rev. Edward G. Coffman Jr., Costas Courcoubetis, Michael R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
2002	J	`jnl`	The Geometric Maximum Traveling Salesman Problem CoRR Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe
2001	A*	`conf`	Better approximation algorithms for bin covering. SODA János Csirik, David S. Johnson, Claire Kenyon
2001	J	`jnl`	Bounded Space On-Line Bin Packing: Best Is Better than First. Algorithmica János Csirik, David S. Johnson
2001	A	`conf`	The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. ALENEX Jill Cirasella, David S. Johnson, Lyle A. McGeoch, Weixiong Zhang
2000	J	`jnl`	Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings. SIAM J. Discret. Math. Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
2000	A*	`conf`	On the sum-of-squares algorithm for bin packing. STOC János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
2000	A*	`conf`	The prize collecting Steiner tree problem: theory and practice. SODA David S. Johnson, Maria Minkoff, Steven Phillips
1999	A	`conf`	A Self Organizing Bin Packing Heuristic. ALENEX János Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
1999	—	`conf`	A theoretician's guide to the experimental analysis of algorithms. Data Structures, Near Neighbor Searches, and Methodology David S. Johnson
1999	A*	`conf`	What are the Least Tractable Instances of max Independent Set? SODA David S. Johnson, Mario Szegedy
1998	B	`conf`	The Maximum Traveling Salesman Problem Under Polyhedral Norms. IPCO Alexander I. Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe
1997	J	`jnl`	Bin packing with discrete item sizes, part II: Tight bounds on First Fit. Random Struct. Algorithms Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber
1997	J	`jnl`	Emerging opportunities for theoretical computer science. SIGACT News Alfred V. Aho, David S. Johnson, Richard M. Karp, S. Rao Kosaraju, Catherine C. McGeoch, Christos H. Papadimitriou, Pavel A. Pevzner
1997	A*	`conf`	Near-optimal Intraprocedural Branch Alignment. PLDI Cliff Young, David S. Johnson, David R. Karger, Michael D. Smith
1997	J	`jnl`	Strategic directions in research in theory of computing. SIGACT News Anne Condon, Faith E. 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
1996	J	`jnl`	A Brief History of SIGACT News and its Editors. SIGACT News David S. Johnson
1996	A*	`conf`	Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound. SODA David S. Johnson, Lyle A. McGeoch, Edward E. Rothberg
1996	—	`ed.`	Cliques, Coloring, and Satisfiability, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 11-13, 1993 Cliques, Coloring, and Satisfiability David S. Johnson, Michael A. Trick
1996	J	`jnl`	How to do experiments (extended advertisement). SIGACT News David S. Johnson
1995	J	`jnl`	Data Structures for Traveling Salesmen. J. Algorithms Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer
1994	A*	`conf`	Minimizing Channel Density by Lateral Shifting of Components. SODA David S. Johnson, Andrea S. LaPaugh, Ron Y. Pinter
1994	B	`conf`	Simulation study of the capacity bounds in cellular systems. PIMRC Zygmunt J. Haas, Jack H. Winters, David S. Johnson
1994	J	`jnl`	The Complexity of Multiterminal Cuts. SIAM J. Comput. Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis
1994	—	`conf`	The Traveling Salesman Problem: A report on the State of the Art. IFIP Congress (1) David S. Johnson
1993	A*	`conf`	Data Structures for Traveling Salesmen. SODA Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer
1993	—	`conf`	Foreword xiIntroduction to the Second DIMACS Challenge: Cliques, coloring, and satisfiability. Cliques, Coloring, and Satisfiability David S. Johnson, Michael A. Trick
1993	A*	`conf`	Markov chains, computer proofs, and average-case analysis of best fit bin packing. STOC Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber
1993	—	`ed.`	Network Flows And Matching, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 14-16, 1991 Network Flows And Matching David S. Johnson, Catherine C. McGeoch
1993	J	`jnl`	Performance of the Efficient Data-Driven Evaluation Scheme. J. Parallel Distributed Comput. David S. Johnson, Francine Berman
1993	A*	`ed.`	Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA STOC S. Rao Kosaraju, David S. Johnson, Alok Aggarwal
1992	A*	`conf`	The Complexity of Multiway Cuts (Extended Abstract) STOC Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis
1992	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1991	—	`conf`	Appendix B: Panel Discussion Highlights. Network Flows And Matching David S. Johnson
1991	A*	`conf`	Bounded Space On-Line Bin Packing: Best is Better than First. SODA János Csirik, David S. Johnson
1991	A*	`conf`	Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study STOC Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
1991	J	`jnl`	Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Oper. Res. David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, Catherine Schevon
1991	—	`conf`	Preface. Network Flows And Matching David S. Johnson, Catherine C. McGeoch
1990	—	`ch.`	A Catalog of Complexity Classes. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) David S. Johnson
1990	J	`jnl`	A stoc/focs bibliography: the last progress report. SIGACT News David S. Johnson
1990	—	`conf`	Data Structures for Traveling Salesmen (Abstract). SWAT David S. Johnson
1990	J	`jnl`	Generalized Planar Matching. J. Algorithms Francine Berman, David S. Johnson, Frank Thomson Leighton, Peter W. Shor, Larry Snyder
1990	A*	`conf`	Local Optimization and the Traveling Salesman Problem. ICALP David S. Johnson
1990	A*	`ed.`	Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California, USA. SODA David S. Johnson
1990	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1990	J	`jnl`	Unit disk graphs. Discret. Math. Brent N. Clark, Charles J. Colbourn, David S. Johnson
1989	Misc	`conf`	Application of VLSI for image processing. ICASSP Richard C. Jaffe, David S. Johnson, Wen-Tai Lin, Chung-Yin Ho
1989	J	`jnl`	Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning. Oper. Res. David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, Catherine Schevon
1989	A*	`ed.`	Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA STOC David S. Johnson
1988	J	`jnl`	How Easy is Local Search? J. Comput. Syst. Sci. David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis
1988	J	`jnl`	On Generating All Maximal Independent Sets. Inf. Process. Lett. David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis
1988	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1988	J	`jnl`	The complexity of searching a graph. J. ACM Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou
1987	J	`jnl`	Bin packing with divisible item sizes. J. Complex. Edward G. Coffman Jr., M. R. Garey, David S. Johnson
1987	J	`jnl`	Hypergraph planarity and the complexity of drawing venn diagrams. J. Graph Theory David S. Johnson, Henry O. Pollak
1987	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1987	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1986	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1986	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1985	J	`jnl`	A 71/60 theorem for bin packing. J. Complex. David S. Johnson, M. R. Garey
1985	J	`jnl`	Composing Functions to Minimize Image Size. SIAM J. Comput. M. R. Garey, David S. Johnson
1985	A*	`conf`	How Easy Is Local Search? (Extended Abstract) FOCS David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis
1985	J	`jnl`	Scheduling File Transfers. SIAM J. Comput. Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh
1985	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1985	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1985	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1984	J	`jnl`	On a Dual Version of the One-Dimensional Bin Packing Problem. J. Algorithms Susan F. Assmann, David S. Johnson, Daniel J. Kleitman, Joseph Y.-T. Leung
1984	A*	`conf`	Some Unexpected Expected Behavior Results for Bin Packing STOC Jon Louis Bentley, David S. Johnson, Frank Thomson Leighton, Catherine C. McGeoch, Lyle A. McGeoch
1984	J	`jnl`	Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. David S. Johnson, Anthony C. Klug
1984	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1984	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1984	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1984	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1984	J	`jnl`	The genealogy of theoretical computer science: a preliminary report. SIGACT News David S. Johnson
1983	J	`jnl`	Dynamic Bin Packing. SIAM J. Comput. Edward G. Coffman Jr., M. R. Garey, David S. Johnson
1983	J	`jnl`	Optimizing Conjunctive Queries that Contain Untyped Variables. SIAM J. Comput. David S. Johnson, Anthony C. Klug
1983	A*	`ed.`	Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA STOC David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, Joel I. Seiferas
1983	A*	`conf`	Scheduling File Transfers in a Distributed Network. PODC Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh
1983	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1983	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1983	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1983	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1982	A*	`conf`	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS David S. Johnson, Anthony C. Klug
1982	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1982	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1982	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1982	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1982	J	`jnl`	The complexity of the generalized Lloyd - Max problem. IEEE Trans. Inf. Theory M. R. Garey, David S. Johnson, Hans S. Witsenhausen
1981	A*	`conf`	Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract) FOCS David S. Johnson, Anthony C. Klug
1981	J	`jnl`	Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines. SIAM J. Comput. M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan
1981	A*	`conf`	The Complexity of Searching a Graph (Preliminary Version) FOCS Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou
1981	J	`jnl`	The NP-Completeness Column: An Ongoing Guide. J. Algorithms David S. Johnson
1980	J	`jnl`	Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM J. Comput. Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan
1980	J	`jnl`	The Complexity of Coloring Circular Arcs and Chords. SIAM J. Algebraic Discret. Methods M. R. Garey, David S. Johnson, Gerald L. Miller, Christos H. Papadimitriou
1979	—	`book`	Computers and Intractability: A Guide to the Theory of NP-Completeness. M. R. Garey, David S. Johnson
1978	J	`jnl`	"Strong" NP-Completeness Results: Motivation, Examples, and Implications. J. ACM M. R. Garey, David S. Johnson
1978	J	`jnl`	A note on "A note on 'Some simplified NP-complete graph problems'". SIGACT News Michael R. Garey, David S. Johnson
1978	J	`jnl`	A note on bisecting minimum spanning trees. Networks William M. Boyce, M. R. Garey, David S. Johnson
1978	J	`jnl`	An Application of Bin-Packing to Multiprocessor Scheduling. SIAM J. Comput. Edward G. Coffman Jr., M. R. Garey, David S. Johnson
1978	J	`jnl`	Performance Guarantees for Scheduling Algorithms. Oper. Res. M. R. Garey, Ronald L. Graham, David S. Johnson
1978	A*	`conf`	The Complexity of Checkers on an N * N Board - Preliminary Report FOCS Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha
1978	J	`jnl`	The Densest Hemisphere Problem. Theor. Comput. Sci. David S. Johnson, Franco P. Preparata
1978	J	`jnl`	The complexity of the network design problem. Networks David S. Johnson, Jan Karel Lenstra, A. H. G. Rinnooy Kan
1978	J	`jnl`	Triangulating a Simple Polygon. Inf. Process. Lett. M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan
1977	J	`jnl`	Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units. IEEE Trans. Computers M. R. Garey, Frank K. Hwang, David S. Johnson
1977	J	`jnl`	Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness. Math. Oper. Res. Peter Brucker, Michael R. Garey, David S. Johnson
1977	J	`jnl`	The Rectilinear Steiner Tree Problem is NP Complete. SIAM Journal of Applied Mathematics M. R. Garey, David S. Johnson
1977	J	`jnl`	Two-Processor Scheduling with Start-Times and Deadlines. SIAM J. Comput. M. R. Garey, David S. Johnson
1976	J	`jnl`	Resource Constrained Scheduling as Generalized Bin Packing. J. Comb. Theory A M. R. Garey, Ronald L. Graham, David S. Johnson, Andrew Chi-Chih Yao
1976	J	`jnl`	Scheduling Tasks with Nonuniform Deadlines on Two Processors. J. ACM M. R. Garey, David S. Johnson
1976	A*	`conf`	Some NP-Complete Geometric Problems STOC M. R. Garey, Ronald L. Graham, David S. Johnson
1976	J	`jnl`	Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. M. R. Garey, David S. Johnson, Larry J. Stockmeyer
1976	J	`jnl`	The Complexity of Flowshop and Jobshop Scheduling. Math. Oper. Res. Michael R. Garey, David S. Johnson, Ravi Sethi
1976	J	`jnl`	The Complexity of Near-Optimal Graph Coloring. J. ACM M. R. Garey, David S. Johnson
1976	J	`jnl`	The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput. M. R. Garey, David S. Johnson, Robert Endre Tarjan
1975	A*	`conf`	An Application of Graph Coloring to Printed Circuit Testing (Working Paper) FOCS M. R. Garey, David S. Johnson, Hing C. So
1975	J	`jnl`	Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM J. Comput. M. R. Garey, David S. Johnson
1974	J	`jnl`	Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. David S. Johnson
1974	J	`jnl`	Fast Algorithms for Bin Packing. J. Comput. Syst. Sci. David S. Johnson
1974	A*	`conf`	Some Simplified NP-Complete Problems STOC M. R. Garey, David S. Johnson, Larry J. Stockmeyer
1974	J	`jnl`	Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM J. Comput. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham
1973	A*	`conf`	Approximation Algorithms for Combinatorial Problems STOC David S. Johnson
1972	—	`conf`	Fast Allocation Algorithms SWAT David S. Johnson