Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: David S. Johnson
@article{DBLP:journals/corr/abs-2306-08933,
author = {David S. Johnson and
Olya Hakobyan and
Hanna Drimalla},
title = {Towards Interpretability in Audio and Visual Affective Machine Learning:
{A} Review},
journal = {CoRR},
volume = {abs/2306.08933},
year = {2023}
}
@inproceedings{DBLP:conf/eusipco/JohnsonLTMGAL21,
author = {David S. Johnson and
Wolfgang Lorenz and
Michael Taenzer and
Stylianos I. Mimilakis and
Sascha Grollmisch and
Jakob Abe{\ss}er and
Hanna M. Lukashevich},
title = {{DESED-FL} and {URBAN-FL:} Federated Learning Datasets for Sound Event
Detection},
booktitle = {{EUSIPCO}},
pages = {556--560},
publisher = {{IEEE}},
year = {2021}
}
@inproceedings{DBLP:conf/samos/AichrothAGGJJKK21,
author = {Patrick Aichroth and
Christoph Antes and
Pierre Gembatzka and
Holger Graf and
David S. Johnson and
Matthias Jung and
Thomas K{\"{a}}mpfe and
Thomas Kleinberger and
Thomas K{\"{o}}llmer and
Thomas Kuhn and
Christoph Kutter and
Jens Kr{\"{u}}ger and
Dominik Marek Loroch and
Hanna M. Lukashevich and
Nellie Laleni and
Lei Zhang and
Johannes Leugering and
Rodrigo Mart{\'{\i}}n Fern{\'{a}}ndez and
Loreto Mateu and
Shaown Mojumder and
Benjamin Prautsch and
Ferdinand Pscheidl and
Karsten Roscher and
S{\"{o}}ren Schneickert and
Frank Vanselow and
Paul Wallbott and
Oliver Walter and
Nico Weber},
title = {SEC-Learn: Sensor Edge Cloud for Federated Learning - Invited Paper},
booktitle = {{SAMOS}},
series = {Lecture Notes in Computer Science},
volume = {13227},
pages = {432--448},
publisher = {Springer},
year = {2021}
}
@article{DBLP:journals/corr/abs-2102-08833,
author = {David S. Johnson and
Wolfgang Lorenz and
Michael Taenzer and
Stylianos I. Mimilakis and
Sascha Grollmisch and
Jakob Abe{\ss}er and
Hanna M. Lukashevich},
title = {{DESED-FL} and {URBAN-FL:} Federated Learning Datasets for Sound Event
Detection},
journal = {CoRR},
volume = {abs/2102.08833},
year = {2021}
}
@article{DBLP:journals/ior/JohnsonBDDGHKRS20,
author = {David S. Johnson and
Lee Breslau and
Ilias Diakonikolas and
Nick Duffield and
Yu Gu and
MohammadTaghi Hajiaghayi and
Howard J. Karloff and
Mauricio G. C. Resende and
Subhabrata Sen},
title = {Near-Optimal Disjoint-Path Facility Location Through Set Cover by
Pairs},
journal = {Oper. Res.},
volume = {68},
number = {3},
pages = {896--926},
year = {2020}
}
@article{DBLP:journals/tcs/GarayJKY20,
author = {Juan A. Garay and
David S. Johnson and
Aggelos Kiayias and
Moti Yung},
title = {The combinatorics of hidden diversity},
journal = {Theor. Comput. Sci.},
volume = {812},
pages = {80--95},
year = {2020}
}
@inproceedings{DBLP:conf/eusipco/JohnsonG20,
author = {David S. Johnson and
Sascha Grollmisch},
title = {Techniques Improving the Robustness of Deep Learning Models for Industrial
Sound Analysis},
booktitle = {{EUSIPCO}},
pages = {81--85},
publisher = {{IEEE}},
year = {2020}
}
@article{DBLP:journals/jco/EpsteinJL18,
author = {Leah Epstein and
David S. Johnson and
Asaf Levin},
title = {Min-Sum Bin Packing},
journal = {J. Comb. Optim.},
volume = {36},
number = {2},
pages = {508--531},
year = {2018}
}
@inproceedings{DBLP:conf/mobihoc/ApplegateAJNTY18,
author = {David L. Applegate and
Aaron Archer and
David S. Johnson and
Evdokia Nikolova and
Mikkel Thorup and
Ger Yang},
title = {Wireless coverage prediction via parametric shortest paths},
booktitle = {MobiHoc},
pages = {221--230},
publisher = {{ACM}},
year = {2018}
}
@article{DBLP:journals/corr/abs-1805-06420,
author = {David L. Applegate and
Aaron Archer and
David S. Johnson and
Evdokia Nikolova and
Mikkel Thorup and
Ger Yang},
title = {Wireless coverage prediction via parametric shortest paths},
journal = {CoRR},
volume = {abs/1805.06420},
year = {2018}
}
@incollection{DBLP:reference/algo/Johnson16,
author = {David S. Johnson},
title = {Bin Packing},
booktitle = {Encyclopedia of Algorithms},
pages = {207--211},
year = {2016}
}
@incollection{DBLP:reference/algo/DemetrescuGJ16,
author = {Camil Demetrescu and
Andrew V. Goldberg and
David S. Johnson},
title = {Implementation Challenge for Shortest Paths},
booktitle = {Encyclopedia of Algorithms},
pages = {947--951},
year = {2016}
}
@incollection{DBLP:reference/algo/Johnson16a,
author = {David S. Johnson},
title = {Vector Bin Packing},
booktitle = {Encyclopedia of Algorithms},
pages = {2319--2323},
year = {2016}
}
@article{DBLP:journals/corr/JohnsonBDD0HKRS16,
author = {David S. Johnson and
Lee Breslau and
Ilias Diakonikolas and
Nick G. Duffield and
Yu Gu and
MohammadTaghi Hajiaghayi and
Howard J. Karloff and
Mauricio G. C. Resende and
Subhabrata Sen},
title = {Near-Optimal Disjoint-Path Facility Location Through Set Cover by
Pairs},
journal = {CoRR},
volume = {abs/1611.01210},
year = {2016}
}
@article{DBLP:journals/dagstuhl-reports/DellingDJV16,
author = {Daniel Delling and
Camil Demetrescu and
David S. Johnson and
Jan Vitek},
title = {Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111)},
journal = {Dagstuhl Reports},
volume = {6},
number = {3},
pages = {24--43},
year = {2016}
}
@inproceedings{DBLP:conf/tcc/GarayGJKY15,
author = {Juan A. Garay and
Ran Gelles and
David S. Johnson and
Aggelos Kiayias and
Moti Yung},
title = {A Little Honesty Goes a Long Way - The Two-Tier Model for Secure Multiparty
Computation},
booktitle = {{TCC} {(1)}},
series = {Lecture Notes in Computer Science},
volume = {9014},
pages = {134--158},
publisher = {Springer},
year = {2015}
}
@article{DBLP:journals/iacr/GarayGJKY14,
author = {Juan A. Garay and
Ran Gelles and
David S. Johnson and
Aggelos Kiayias and
Moti Yung},
title = {A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty
Computation},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {209},
year = {2014}
}
@inproceedings{DBLP:conf/innovations/GarayJKY13,
author = {Juan A. Garay and
David S. Johnson and
Aggelos Kiayias and
Moti Yung},
title = {Resource-based corruptions and the combinatorics of hidden diversity},
booktitle = {{ITCS}},
pages = {415--428},
publisher = {{ACM}},
year = {2013}
}
@article{DBLP:journals/dagstuhl-reports/GoldbergIJW13,
author = {Andrew V. Goldberg and
Giuseppe F. Italiano and
David S. Johnson and
Dorothea Wagner},
title = {Algorithm Engineering (Dagstuhl Seminar 13391)},
journal = {Dagstuhl Reports},
volume = {3},
number = {9},
pages = {169--189},
year = {2013}
}
@article{DBLP:journals/iacr/GarayJKY12,
author = {Juan A. Garay and
David S. Johnson and
Aggelos Kiayias and
Moti Yung},
title = {Resource-based Corruptions and the Combinatorics of Hidden Diversity},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {556},
year = {2012}
}
@inproceedings{DBLP:conf/alenex/BreslauDDGHJKRS11,
author = {Lee Breslau and
Ilias Diakonikolas and
Nick G. Duffield and
Yu Gu and
Mohammad Taghi Hajiaghayi and
David S. Johnson and
Howard J. Karloff and
Mauricio G. C. Resende and
Subhabrata Sen},
title = {Disjoint-Path Facility Location: Theory and Practice},
booktitle = {{ALENEX}},
pages = {60--74},
publisher = {{SIAM}},
year = {2011}
}
@proceedings{DBLP:conf/dagstuhl/2010P10261,
editor = {Giuseppe F. Italiano and
David S. Johnson and
Petra Mutzel and
Peter Sanders},
title = {Algorithm Engineering, 27.06. - 02.07.2010},
series = {Dagstuhl Seminar Proceedings},
volume = {10261},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2010}
}
@inproceedings{DBLP:conf/dagstuhl/ItalianoJMS10,
author = {Giuseppe F. Italiano and
David S. Johnson and
Petra Mutzel and
Peter Sanders},
title = {10261 Abstracts Collection - Algorithm Engineering},
booktitle = {Algorithm Engineering},
series = {Dagstuhl Seminar Proceedings},
volume = {10261},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2010}
}
@inproceedings{DBLP:conf/dagstuhl/ItalianoJMS10a,
author = {Giuseppe F. Italiano and
David S. Johnson and
Petra Mutzel and
Peter Sanders},
title = {10261 Executive Summary - Algorithm Engineering},
booktitle = {Algorithm Engineering},
series = {Dagstuhl Seminar Proceedings},
volume = {10261},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2010}
}
@proceedings{DBLP:conf/dimacs/dimacs74,
editor = {Camil Demetrescu and
Andrew V. Goldberg and
David S. Johnson},
title = {The Shortest Path Problem, Proceedings of a {DIMACS} Workshop, Piscataway,
New Jersey, USA, November 13-14, 2006},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {74},
publisher = {{DIMACS/AMS}},
year = {2009}
}
@article{DBLP:journals/dam/JohnsonMT08,
author = {David S. Johnson and
Anuj Mehrotra and
Michael A. Trick},
title = {Special issue on computational methods for graph coloring and its
generalizations},
journal = {Discret. Appl. Math.},
volume = {156},
number = {2},
pages = {145--146},
year = {2008}
}
@incollection{DBLP:reference/algo/DemetrescuGJ08,
author = {Camil Demetrescu and
Andrew V. Goldberg and
David S. Johnson},
title = {Implementation Challenge for Shortest Paths},
booktitle = {Encyclopedia of Algorithms},
publisher = {Springer},
year = {2008}
}
@incollection{DBLP:reference/algo/Johnson08,
author = {David S. Johnson},
title = {Bin Packing},
booktitle = {Encyclopedia of Algorithms},
publisher = {Springer},
year = {2008}
}
@article{DBLP:journals/talg/Johnson07,
author = {David S. Johnson},
title = {The NP-completeness column: Finding needles in haystacks},
journal = {{ACM} Trans. Algorithms},
volume = {3},
number = {2},
pages = {24},
year = {2007}
}
@inproceedings{DBLP:conf/expcs/Johnson07,
author = {David S. Johnson},
title = {What is the science in experimental computer science?},
booktitle = {Experimental Computer Science},
pages = {1},
publisher = {{ACM}},
year = {2007}
}
@inproceedings{DBLP:conf/soda/ApplegateCJKLW07,
author = {David L. Applegate and
Gruia C{\u{a}}linescu and
David S. Johnson and
Howard J. Karloff and
Katrina Ligett and
Jia Wang},
title = {Compressing rectilinear pictures and minimizing access control lists},
booktitle = {{SODA}},
pages = {1066--1075},
publisher = {{SIAM}},
year = {2007}
}
@proceedings{DBLP:conf/stoc/2007,
editor = {David S. Johnson and
Uriel Feige},
title = {Proceedings of the 39th Annual {ACM} Symposium on Theory of Computing,
San Diego, California, USA, June 11-13, 2007},
publisher = {{ACM}},
year = {2007}
}
@article{DBLP:journals/jacm/CsirikJKOSW06,
author = {J{\'{a}}nos Csirik and
David S. Johnson and
Claire Kenyon and
James B. Orlin and
Peter W. Shor and
Richard R. Weber},
title = {On the Sum-of-Squares algorithm for bin packing},
journal = {J. {ACM}},
volume = {53},
number = {1},
pages = {1--65},
year = {2006}
}
@article{DBLP:journals/talg/Johnson06,
author = {David S. Johnson},
title = {The NP-completeness column: The many limits on approximation},
journal = {{ACM} Trans. Algorithms},
volume = {2},
number = {3},
pages = {473--489},
year = {2006}
}
@article{DBLP:journals/talg/Johnson05,
author = {David S. Johnson},
title = {The NP-completeness column},
journal = {{ACM} Trans. Algorithms},
volume = {1},
number = {1},
pages = {160--176},
year = {2005}
}
@article{DBLP:journals/tvcg/ChhuganiPKCVJK05,
author = {Jatin Chhugani and
Budirijanto Purnomo and
Shankar Krishnan and
Jonathan D. Cohen and
Suresh Venkatasubramanian and
David S. Johnson and
Subodh Kumar},
title = {vLOD: High-Fidelity Walkthrough of Large Virtual Environments},
journal = {{IEEE} Trans. Vis. Comput. Graph.},
volume = {11},
number = {1},
pages = {35--47},
year = {2005}
}
@article{DBLP:journals/corr/abs-cs-0509031,
author = {J{\'{a}}nos Csirik and
David S. Johnson and
Claire Kenyon},
title = {On the Worst-case Performance of the Sum-of-Squares Algorithm for
Bin Packing},
journal = {CoRR},
volume = {abs/cs/0509031},
year = {2005}
}
@inproceedings{DBLP:conf/vldb/JohnsonKCKV04,
author = {David S. Johnson and
Shankar Krishnan and
Jatin Chhugani and
Subodh Kumar and
Suresh Venkatasubramanian},
title = {Compressing Large Boolean Matrices using Reordering Techniques},
booktitle = {{VLDB}},
pages = {13--23},
publisher = {Morgan Kaufmann},
year = {2004}
}
@article{DBLP:journals/jacm/BarvinokFJTWW03,
author = {Alexander I. Barvinok and
S{\'{a}}ndor P. Fekete and
David S. Johnson and
Arie Tamir and
Gerhard J. Woeginger and
Russell Woodroofe},
title = {The geometric maximum traveling salesman problem},
journal = {J. {ACM}},
volume = {50},
number = {5},
pages = {641--664},
year = {2003}
}
@inproceedings{DBLP:conf/alenex/ApplegateBDJS03,
author = {David L. Applegate and
Luciana S. Buriol and
Bernard L. Dillard and
David S. Johnson and
Peter W. Shor},
title = {The Cutting-Stock Approach to Bin Packing: Theory and Experiments},
booktitle = {{ALENEX}},
pages = {1--15},
publisher = {{SIAM}},
year = {2003}
}
@article{DBLP:journals/siamrev/CoffmanCGJSWY02,
author = {Edward G. Coffman Jr. and
Costas Courcoubetis and
Michael R. Garey and
David S. Johnson and
Peter W. Shor and
Richard R. Weber and
Mihalis Yannakakis},
title = {Perfect Packing Theorems and the Average-Case Behavior of Optimal
and Online Bin Packing},
journal = {{SIAM} Rev.},
volume = {44},
number = {1},
pages = {95--108},
year = {2002}
}
@proceedings{DBLP:conf/dimacs/dimacs59,
editor = {Michael H. Goldwasser and
David S. Johnson and
Catherine C. McGeoch},
title = {Data Structures, Near Neighbor Searches, and Methodology: Fifth and
Sixth {DIMACS} Implementation Challenges, Proceedings of a {DIMACS}
Workshop, USA, 1999},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {59},
publisher = {{DIMACS/AMS}},
year = {2002}
}
@article{DBLP:journals/corr/cs-DS-0204024,
author = {Alexander I. Barvinok and
S{\'{a}}ndor P. Fekete and
David S. Johnson and
Arie Tamir and
Gerhard J. Woeginger and
Russell Woodroofe},
title = {The Geometric Maximum Traveling Salesman Problem},
journal = {CoRR},
volume = {cs.DS/0204024},
year = {2002}
}
@article{DBLP:journals/corr/cs-DS-0210013,
author = {J{\'{a}}nos Csirik and
David S. Johnson and
Claire Kenyon and
James B. Orlin and
Peter W. Shor and
Richard R. Weber},
title = {On the Sum-of-Squares Algorithm for Bin Packing},
journal = {CoRR},
volume = {cs.DS/0210013},
year = {2002}
}
@article{DBLP:journals/algorithmica/CsirikJ01,
author = {J{\'{a}}nos Csirik and
David S. Johnson},
title = {Bounded Space On-Line Bin Packing: Best Is Better than First},
journal = {Algorithmica},
volume = {31},
number = {2},
pages = {115--138},
year = {2001}
}
@inproceedings{DBLP:conf/alenex/CirasellaJMZ01,
author = {Jill Cirasella and
David S. Johnson and
Lyle A. McGeoch and
Weixiong Zhang},
title = {The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators,
and Tests},
booktitle = {{ALENEX}},
series = {Lecture Notes in Computer Science},
volume = {2153},
pages = {32--59},
publisher = {Springer},
year = {2001}
}
@inproceedings{DBLP:conf/soda/CsirikJK01,
author = {J{\'{a}}nos Csirik and
David S. Johnson and
Claire Kenyon},
title = {Better approximation algorithms for bin covering},
booktitle = {{SODA}},
pages = {557--566},
publisher = {{ACM/SIAM}},
year = {2001}
}
@article{DBLP:journals/siamdm/CoffmanCGJSWY00,
author = {Edward G. Coffman Jr. and
Costas Courcoubetis and
M. R. Garey and
David S. Johnson and
Peter W. Shor and
Richard R. Weber and
Mihalis Yannakakis},
title = {Bin Packing with Discrete Item Sizes, Part {I:} Perfect Packing Theorems
and the Average Case Behavior of Optimal Packings},
journal = {{SIAM} J. Discret. Math.},
volume = {13},
number = {3},
pages = {384--402},
year = {2000}
}
@inproceedings{DBLP:conf/soda/JohnsonMP00,
author = {David S. Johnson and
Maria Minkoff and
Steven Phillips},
title = {The prize collecting Steiner tree problem: theory and practice},
booktitle = {{SODA}},
pages = {760--769},
publisher = {{ACM/SIAM}},
year = {2000}
}
@inproceedings{DBLP:conf/stoc/CsirikJKOSW00,
author = {J{\'{a}}nos Csirik and
David S. Johnson and
Claire Kenyon and
James B. Orlin and
Peter W. Shor and
Richard R. Weber},
title = {On the sum-of-squares algorithm for bin packing},
booktitle = {{STOC}},
pages = {208--217},
publisher = {{ACM}},
year = {2000}
}
@inproceedings{DBLP:conf/alenex/CsirikJKSW99,
author = {J{\'{a}}nos Csirik and
David S. Johnson and
Claire Kenyon and
Peter W. Shor and
Richard R. Weber},
title = {A Self Organizing Bin Packing Heuristic},
booktitle = {{ALENEX}},
series = {Lecture Notes in Computer Science},
volume = {1619},
pages = {246--265},
publisher = {Springer},
year = {1999}
}
@inproceedings{DBLP:conf/dimacs/Johnson99,
author = {David S. Johnson},
title = {A theoretician's guide to the experimental analysis of algorithms},
booktitle = {Data Structures, Near Neighbor Searches, and Methodology},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {59},
pages = {215--250},
publisher = {{DIMACS/AMS}},
year = {1999}
}
@inproceedings{DBLP:conf/soda/JohnsonS99,
author = {David S. Johnson and
Mario Szegedy},
title = {What are the Least Tractable Instances of max Independent Set?},
booktitle = {{SODA}},
pages = {927--928},
publisher = {{ACM/SIAM}},
year = {1999}
}
@inproceedings{DBLP:conf/ipco/BarvinokJWW98,
author = {Alexander I. Barvinok and
David S. Johnson and
Gerhard J. Woeginger and
Russell Woodroofe},
title = {The Maximum Traveling Salesman Problem Under Polyhedral Norms},
booktitle = {{IPCO}},
series = {Lecture Notes in Computer Science},
volume = {1412},
pages = {195--201},
publisher = {Springer},
year = {1998}
}
@article{DBLP:journals/rsa/CoffmanJSW97,
author = {Edward G. Coffman Jr. and
David S. Johnson and
Peter W. Shor and
Richard R. Weber},
title = {Bin packing with discrete item sizes, part {II:} Tight bounds on First
Fit},
journal = {Random Struct. Algorithms},
volume = {10},
number = {1-2},
pages = {69--101},
year = {1997}
}
@article{DBLP:journals/sigact/AhoJKKMPP97,
author = {Alfred V. Aho and
David S. Johnson and
Richard M. Karp and
S. Rao Kosaraju and
Catherine C. McGeoch and
Christos H. Papadimitriou and
Pavel A. Pevzner},
title = {Emerging opportunities for theoretical computer science},
journal = {{SIGACT} News},
volume = {28},
number = {3},
pages = {65--74},
year = {1997}
}
@article{DBLP:journals/sigact/CondonFFGJLMRSSS97,
author = {Anne Condon and
Faith E. Fich and
Greg N. Frederickson and
Andrew V. Goldberg and
David S. Johnson and
Michael C. Loui and
Steven Mahaney and
Prabhakar Raghavan and
John E. Savage and
Alan L. Selman and
David B. Shmoys},
title = {Strategic directions in research in theory of computing},
journal = {{SIGACT} News},
volume = {28},
number = {3},
pages = {75--93},
year = {1997}
}
@inproceedings{DBLP:conf/pldi/YoungJKS97,
author = {Cliff Young and
David S. Johnson and
David R. Karger and
Michael D. Smith},
title = {Near-optimal Intraprocedural Branch Alignment},
booktitle = {{PLDI}},
pages = {183--193},
publisher = {{ACM}},
year = {1997}
}
@article{DBLP:journals/sigact/Johnson96,
author = {David S. Johnson},
title = {How to do experiments (extended advertisement)},
journal = {{SIGACT} News},
volume = {27},
number = {2},
pages = {87},
year = {1996}
}
@article{DBLP:journals/sigact/Johnson96a,
author = {David S. Johnson},
title = {A Brief History of {SIGACT} News and its Editors},
journal = {{SIGACT} News},
volume = {27},
number = {3},
pages = {125},
year = {1996}
}
@inproceedings{DBLP:conf/soda/JohnsonMR96,
author = {David S. Johnson and
Lyle A. McGeoch and
Edward E. Rothberg},
title = {Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman
Bound},
booktitle = {{SODA}},
pages = {341--350},
publisher = {{ACM/SIAM}},
year = {1996}
}
@proceedings{DBLP:conf/dimacs/dimacs26,
editor = {David S. Johnson and
Michael A. Trick},
title = {Cliques, Coloring, and Satisfiability, Proceedings of a {DIMACS} Workshop,
New Brunswick, New Jersey, USA, October 11-13, 1993},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {26},
publisher = {{DIMACS/AMS}},
year = {1996}
}
@article{DBLP:journals/jal/FredmanJMO95,
author = {Michael L. Fredman and
David S. Johnson and
Lyle A. McGeoch and
G. Ostheimer},
title = {Data Structures for Traveling Salesmen},
journal = {J. Algorithms},
volume = {18},
number = {3},
pages = {432--479},
year = {1995}
}
@article{DBLP:journals/siamcomp/DahlhausJPSY94,
author = {Elias Dahlhaus and
David S. Johnson and
Christos H. Papadimitriou and
Paul D. Seymour and
Mihalis Yannakakis},
title = {The Complexity of Multiterminal Cuts},
journal = {{SIAM} J. Comput.},
volume = {23},
number = {4},
pages = {864--894},
year = {1994}
}
@inproceedings{DBLP:conf/ifip/Johnson94,
author = {David S. Johnson},
title = {The Traveling Salesman Problem: {A} report on the State of the Art},
booktitle = {{IFIP} Congress {(1)}},
series = {{IFIP} Transactions},
volume = {{A-51}},
pages = {221--222},
publisher = {North-Holland},
year = {1994}
}
@inproceedings{DBLP:conf/pimrc/HaasWJ94,
author = {Zygmunt J. Haas and
Jack H. Winters and
David S. Johnson},
title = {Simulation study of the capacity bounds in cellular systems},
booktitle = {{PIMRC}},
pages = {1114--1120},
year = {1994}
}
@inproceedings{DBLP:conf/soda/JohnsonLP94,
author = {David S. Johnson and
Andrea S. LaPaugh and
Ron Y. Pinter},
title = {Minimizing Channel Density by Lateral Shifting of Components},
booktitle = {{SODA}},
pages = {122--131},
publisher = {{ACM/SIAM}},
year = {1994}
}
@article{DBLP:journals/jpdc/JohnsonB93,
author = {David S. Johnson and
Francine Berman},
title = {Performance of the Efficient Data-Driven Evaluation Scheme},
journal = {J. Parallel Distributed Comput.},
volume = {18},
number = {3},
pages = {340--346},
year = {1993}
}
@inproceedings{DBLP:conf/dimacs/JohnsonT93,
author = {David S. Johnson and
Michael A. Trick},
title = {Foreword xiIntroduction to the Second {DIMACS} Challenge: Cliques,
coloring, and satisfiability},
booktitle = {Cliques, Coloring, and Satisfiability},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {26},
pages = {1--7},
publisher = {{DIMACS/AMS}},
year = {1993}
}
@inproceedings{DBLP:conf/soda/FredmanJMO93,
author = {Michael L. Fredman and
David S. Johnson and
Lyle A. McGeoch and
G. Ostheimer},
title = {Data Structures for Traveling Salesmen},
booktitle = {{SODA}},
pages = {145--154},
publisher = {{ACM/SIAM}},
year = {1993}
}
@inproceedings{DBLP:conf/stoc/CoffmanJSW93,
author = {Edward G. Coffman Jr. and
David S. Johnson and
Peter W. Shor and
Richard R. Weber},
title = {Markov chains, computer proofs, and average-case analysis of best
fit bin packing},
booktitle = {{STOC}},
pages = {412--421},
publisher = {{ACM}},
year = {1993}
}
@proceedings{DBLP:conf/dimacs/dimacs12,
editor = {David S. Johnson and
Catherine C. McGeoch},
title = {Network Flows And Matching, Proceedings of a {DIMACS} Workshop, New
Brunswick, New Jersey, USA, October 14-16, 1991},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {12},
publisher = {{DIMACS/AMS}},
year = {1993}
}
@proceedings{DBLP:conf/stoc/STOC25,
editor = {S. Rao Kosaraju and
David S. Johnson and
Alok Aggarwal},
title = {Proceedings of the Twenty-Fifth Annual {ACM} Symposium on Theory of
Computing, May 16-18, 1993, San Diego, CA, {USA}},
publisher = {{ACM}},
year = {1993}
}
@article{DBLP:journals/jal/Johnson92,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {13},
number = {3},
pages = {502--524},
year = {1992}
}
@inproceedings{DBLP:conf/stoc/DahlhausJPSY92,
author = {Elias Dahlhaus and
David S. Johnson and
Christos H. Papadimitriou and
Paul D. Seymour and
Mihalis Yannakakis},
title = {The Complexity of Multiway Cuts (Extended Abstract)},
booktitle = {{STOC}},
pages = {241--251},
publisher = {{ACM}},
year = {1992}
}
@article{DBLP:journals/ior/JohnsonAMS91,
author = {David S. Johnson and
Cecilia R. Aragon and
Lyle A. McGeoch and
Catherine Schevon},
title = {Optimization by Simulated Annealing: An Experimental Evaluation; Part
II, Graph Coloring and Number Partitioning},
journal = {Oper. Res.},
volume = {39},
number = {3},
pages = {378--406},
year = {1991}
}
@inproceedings{DBLP:conf/dimacs/Johnson91,
author = {David S. Johnson},
title = {Appendix {B:} Panel Discussion Highlights},
booktitle = {Network Flows And Matching},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {12},
pages = {583--592},
publisher = {{DIMACS/AMS}},
year = {1991}
}
@inproceedings{DBLP:conf/dimacs/JohnsonM91,
author = {David S. Johnson and
Catherine C. McGeoch},
title = {Preface},
booktitle = {Network Flows And Matching},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {12},
pages = {xi},
publisher = {{DIMACS/AMS}},
year = {1991}
}
@inproceedings{DBLP:conf/soda/CsirikJ91,
author = {J{\'{a}}nos Csirik and
David S. Johnson},
title = {Bounded Space On-Line Bin Packing: Best is Better than First},
booktitle = {{SODA}},
pages = {309--319},
publisher = {{ACM/SIAM}},
year = {1991}
}
@inproceedings{DBLP:conf/stoc/CoffmanCGJMSWY91,
author = {Edward G. Coffman Jr. and
Costas Courcoubetis and
M. R. Garey and
David S. Johnson and
Lyle A. McGeoch and
Peter W. Shor and
Richard R. Weber and
Mihalis Yannakakis},
title = {Fundamental Discrepancies between Average-Case Analyses under Discrete
and Continuous Distributions: {A} Bin Packing Case Study},
booktitle = {{STOC}},
pages = {230--240},
publisher = {{ACM}},
year = {1991}
}
@article{DBLP:journals/dm/ClarkCJ90,
author = {Brent N. Clark and
Charles J. Colbourn and
David S. Johnson},
title = {Unit disk graphs},
journal = {Discret. Math.},
volume = {86},
number = {1-3},
pages = {165--177},
year = {1990}
}
@article{DBLP:journals/jal/Johnson90,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {11},
number = {1},
pages = {144--151},
year = {1990}
}
@article{DBLP:journals/jal/BermanJLSS90,
author = {Francine Berman and
David S. Johnson and
Frank Thomson Leighton and
Peter W. Shor and
Larry Snyder},
title = {Generalized Planar Matching},
journal = {J. Algorithms},
volume = {11},
number = {2},
pages = {153--184},
year = {1990}
}
@article{DBLP:journals/sigact/Johnson90,
author = {David S. Johnson},
title = {A stoc/focs bibliography: the last progress report},
journal = {{SIGACT} News},
volume = {21},
number = {2},
pages = {4},
year = {1990}
}
@inproceedings{DBLP:conf/icalp/Johnson90,
author = {David S. Johnson},
title = {Local Optimization and the Traveling Salesman Problem},
booktitle = {{ICALP}},
series = {Lecture Notes in Computer Science},
volume = {443},
pages = {446--461},
publisher = {Springer},
year = {1990}
}
@inproceedings{DBLP:conf/swat/Johnson90,
author = {David S. Johnson},
title = {Data Structures for Traveling Salesmen (Abstract)},
booktitle = {{SWAT}},
series = {Lecture Notes in Computer Science},
volume = {447},
pages = {287},
publisher = {Springer},
year = {1990}
}
@incollection{DBLP:books/el/leeuwen90/Johnson90,
author = {David S. Johnson},
title = {A Catalog of Complexity Classes},
booktitle = {Handbook of Theoretical Computer Science, Volume {A:} Algorithms and
Complexity {(A)}},
pages = {67--161},
publisher = {Elsevier and {MIT} Press},
year = {1990}
}
@proceedings{DBLP:conf/soda/1990,
editor = {David S. Johnson},
title = {Proceedings of the First Annual {ACM-SIAM} Symposium on Discrete Algorithms,
22-24 January 1990, San Francisco, California, {USA}},
publisher = {{SIAM}},
year = {1990}
}
@article{DBLP:journals/ior/JohnsonAMS89,
author = {David S. Johnson and
Cecilia R. Aragon and
Lyle A. McGeoch and
Catherine Schevon},
title = {Optimization by Simulated Annealing: An Experimental Evaluation; Part
I, Graph Partitioning},
journal = {Oper. Res.},
volume = {37},
number = {6},
pages = {865--892},
year = {1989}
}
@inproceedings{DBLP:conf/icassp/JaffeJLH89,
author = {Richard C. Jaffe and
David S. Johnson and
Wen{-}Tai Lin and
Chung{-}Yin Ho},
title = {Application of {VLSI} for image processing},
booktitle = {{ICASSP}},
pages = {2421--2424},
publisher = {{IEEE}},
year = {1989}
}
@proceedings{DBLP:conf/stoc/STOC21,
editor = {David S. Johnson},
title = {Proceedings of the 21st Annual {ACM} Symposium on Theory of Computing,
May 14-17, 1989, Seattle, Washington, {USA}},
publisher = {{ACM}},
year = {1989}
}
@article{DBLP:journals/ipl/JohnsonP88,
author = {David S. Johnson and
Christos H. Papadimitriou and
Mihalis Yannakakis},
title = {On Generating All Maximal Independent Sets},
journal = {Inf. Process. Lett.},
volume = {27},
number = {3},
pages = {119--123},
year = {1988}
}
@article{DBLP:journals/jacm/MegiddoHGJP88,
author = {Nimrod Megiddo and
S. Louis Hakimi and
M. R. Garey and
David S. Johnson and
Christos H. Papadimitriou},
title = {The complexity of searching a graph},
journal = {J. {ACM}},
volume = {35},
number = {1},
pages = {18--44},
year = {1988}
}
@article{DBLP:journals/jal/Johnson88,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {9},
number = {3},
pages = {426--444},
year = {1988}
}
@article{DBLP:journals/jcss/JohnsonPY88,
author = {David S. Johnson and
Christos H. Papadimitriou and
Mihalis Yannakakis},
title = {How Easy is Local Search?},
journal = {J. Comput. Syst. Sci.},
volume = {37},
number = {1},
pages = {79--100},
year = {1988}
}
@article{DBLP:journals/jal/Johnson87,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {8},
number = {2},
pages = {285--303},
year = {1987}
}
@article{DBLP:journals/jal/Johnson87a,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {8},
number = {3},
pages = {438--448},
year = {1987}
}
@article{DBLP:journals/jc/CoffmanGJ87,
author = {Edward G. Coffman Jr. and
M. R. Garey and
David S. Johnson},
title = {Bin packing with divisible item sizes},
journal = {J. Complex.},
volume = {3},
number = {4},
pages = {406--428},
year = {1987}
}
@article{DBLP:journals/jgt/JohnsonP87,
author = {David S. Johnson and
Henry O. Pollak},
title = {Hypergraph planarity and the complexity of drawing venn diagrams},
journal = {J. Graph Theory},
volume = {11},
number = {3},
pages = {309--325},
year = {1987}
}
@article{DBLP:journals/jal/Johnson86,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {7},
number = {2},
pages = {289--305},
year = {1986}
}
@article{DBLP:journals/jal/Johnson86a,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {7},
number = {4},
pages = {584--601},
year = {1986}
}
@article{DBLP:journals/jal/Johnson85,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {6},
number = {1},
pages = {145--159},
year = {1985}
}
@article{DBLP:journals/jal/Johnson85a,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {6},
number = {2},
pages = {291--305},
year = {1985}
}
@article{DBLP:journals/jal/Johnson85b,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {6},
number = {3},
pages = {434--451},
year = {1985}
}
@article{DBLP:journals/jc/JohnsonG85,
author = {David S. Johnson and
M. R. Garey},
title = {A 71/60 theorem for bin packing},
journal = {J. Complex.},
volume = {1},
number = {1},
pages = {65--106},
year = {1985}
}
@article{DBLP:journals/siamcomp/GareyJ85,
author = {M. R. Garey and
David S. Johnson},
title = {Composing Functions to Minimize Image Size},
journal = {{SIAM} J. Comput.},
volume = {14},
number = {2},
pages = {500--503},
year = {1985}
}
@article{DBLP:journals/siamcomp/CoffmanGJL85,
author = {Edward G. Coffman Jr. and
M. R. Garey and
David S. Johnson and
Andrea S. LaPaugh},
title = {Scheduling File Transfers},
journal = {{SIAM} J. Comput.},
volume = {14},
number = {3},
pages = {744--780},
year = {1985}
}
@inproceedings{DBLP:conf/focs/JohnsonPY85,
author = {David S. Johnson and
Christos H. Papadimitriou and
Mihalis Yannakakis},
title = {How Easy Is Local Search? (Extended Abstract)},
booktitle = {{FOCS}},
pages = {39--42},
publisher = {{IEEE} Computer Society},
year = {1985}
}
@article{DBLP:journals/jal/Johnson84,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {5},
number = {1},
pages = {147--160},
year = {1984}
}
@article{DBLP:journals/jal/Johnson84a,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {5},
number = {2},
pages = {284--299},
year = {1984}
}
@article{DBLP:journals/jal/Johnson84b,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {5},
number = {3},
pages = {433--447},
year = {1984}
}
@article{DBLP:journals/jal/AssmannJKL84,
author = {Susan F. Assmann and
David S. Johnson and
Daniel J. Kleitman and
Joseph Y.{-}T. Leung},
title = {On a Dual Version of the One-Dimensional Bin Packing Problem},
journal = {J. Algorithms},
volume = {5},
number = {4},
pages = {502--525},
year = {1984}
}
@article{DBLP:journals/jal/Johnson84c,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {5},
number = {4},
pages = {595--609},
year = {1984}
}
@article{DBLP:journals/jcss/JohnsonK84,
author = {David S. Johnson and
Anthony C. Klug},
title = {Testing Containment of Conjunctive Queries under Functional and Inclusion
Dependencies},
journal = {J. Comput. Syst. Sci.},
volume = {28},
number = {1},
pages = {167--189},
year = {1984}
}
@article{DBLP:journals/sigact/Johnson84,
author = {David S. Johnson},
title = {The genealogy of theoretical computer science: a preliminary report},
journal = {{SIGACT} News},
volume = {16},
number = {2},
pages = {36--49},
year = {1984}
}
@inproceedings{DBLP:conf/stoc/BentleyJLMM84,
author = {Jon Louis Bentley and
David S. Johnson and
Frank Thomson Leighton and
Catherine C. McGeoch and
Lyle A. McGeoch},
title = {Some Unexpected Expected Behavior Results for Bin Packing},
booktitle = {{STOC}},
pages = {279--288},
publisher = {{ACM}},
year = {1984}
}
@article{DBLP:journals/jal/Johnson83,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {4},
number = {1},
pages = {87--100},
year = {1983}
}
@article{DBLP:journals/jal/Johnson83a,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {4},
number = {2},
pages = {189--203},
year = {1983}
}
@article{DBLP:journals/jal/Johnson83b,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {4},
number = {3},
pages = {286--300},
year = {1983}
}
@article{DBLP:journals/jal/Johnson83c,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {4},
number = {4},
pages = {397--411},
year = {1983}
}
@article{DBLP:journals/siamcomp/CoffmanGJ83,
author = {Edward G. Coffman Jr. and
M. R. Garey and
David S. Johnson},
title = {Dynamic Bin Packing},
journal = {{SIAM} J. Comput.},
volume = {12},
number = {2},
pages = {227--258},
year = {1983}
}
@article{DBLP:journals/siamcomp/JohnsonK83,
author = {David S. Johnson and
Anthony C. Klug},
title = {Optimizing Conjunctive Queries that Contain Untyped Variables},
journal = {{SIAM} J. Comput.},
volume = {12},
number = {4},
pages = {616--640},
year = {1983}
}
@inproceedings{DBLP:conf/podc/CoffmanGJL83,
author = {Edward G. Coffman Jr. and
M. R. Garey and
David S. Johnson and
Andrea S. LaPaugh},
title = {Scheduling File Transfers in a Distributed Network},
booktitle = {{PODC}},
pages = {254--266},
publisher = {{ACM}},
year = {1983}
}
@proceedings{DBLP:conf/stoc/STOC15,
editor = {David S. Johnson and
Ronald Fagin and
Michael L. Fredman and
David Harel and
Richard M. Karp and
Nancy A. Lynch and
Christos H. Papadimitriou and
Ronald L. Rivest and
Walter L. Ruzzo and
Joel I. Seiferas},
title = {Proceedings of the 15th Annual {ACM} Symposium on Theory of Computing,
25-27 April, 1983, Boston, Massachusetts, {USA}},
publisher = {{ACM}},
year = {1983}
}
@article{DBLP:journals/jal/Johnson82c,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {3},
number = {1},
pages = {89--99},
year = {1982}
}
@article{DBLP:journals/jal/Johnson82,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {3},
number = {2},
pages = {182--195},
year = {1982}
}
@article{DBLP:journals/jal/Johnson82a,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {3},
number = {3},
pages = {288--300},
year = {1982}
}
@article{DBLP:journals/jal/Johnson82b,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {3},
number = {4},
pages = {381--395},
year = {1982}
}
@article{DBLP:journals/tit/GareyJW82,
author = {M. R. Garey and
David S. Johnson and
Hans S. Witsenhausen},
title = {The complexity of the generalized Lloyd - Max problem},
journal = {{IEEE} Trans. Inf. Theory},
volume = {28},
number = {2},
pages = {255--256},
year = {1982}
}
@inproceedings{DBLP:conf/pods/JohnsonK82,
author = {David S. Johnson and
Anthony C. Klug},
title = {Testing Containment of Conjunctive Queries Under Functional and Inclusion
Dependencies},
booktitle = {{PODS}},
pages = {164--169},
publisher = {{ACM}},
year = {1982}
}
@article{DBLP:journals/jal/Johnson81,
author = {David S. Johnson},
title = {The NP-Completeness Column: An Ongoing Guide},
journal = {J. Algorithms},
volume = {2},
number = {4},
pages = {393--405},
year = {1981}
}
@article{DBLP:journals/siamcomp/GareyJST81,
author = {M. R. Garey and
David S. Johnson and
Barbara B. Simons and
Robert Endre Tarjan},
title = {Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines},
journal = {{SIAM} J. Comput.},
volume = {10},
number = {2},
pages = {256--269},
year = {1981}
}
@inproceedings{DBLP:conf/focs/JohnsonK81,
author = {David S. Johnson and
Anthony C. Klug},
title = {Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint
(Extended Abstract)},
booktitle = {{FOCS}},
pages = {203--211},
publisher = {{IEEE} Computer Society},
year = {1981}
}
@inproceedings{DBLP:conf/focs/MegiddoHGJP81,
author = {Nimrod Megiddo and
S. Louis Hakimi and
M. R. Garey and
David S. Johnson and
Christos H. Papadimitriou},
title = {The Complexity of Searching a Graph (Preliminary Version)},
booktitle = {{FOCS}},
pages = {376--385},
publisher = {{IEEE} Computer Society},
year = {1981}
}
@article{DBLP:journals/siamcomp/CoffmanGJT80,
author = {Edward G. Coffman Jr. and
M. R. Garey and
David S. Johnson and
Robert Endre Tarjan},
title = {Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms},
journal = {{SIAM} J. Comput.},
volume = {9},
number = {4},
pages = {808--826},
year = {1980}
}
@article{DBLP:journals/siammax/GareyJMP80,
author = {M. R. Garey and
David S. Johnson and
Gerald L. Miller and
Christos H. Papadimitriou},
title = {The Complexity of Coloring Circular Arcs and Chords},
journal = {{SIAM} J. Algebraic Discret. Methods},
volume = {1},
number = {2},
pages = {216--227},
year = {1980}
}
@book{DBLP:books/fm/GareyJ79,
author = {M. R. Garey and
David S. Johnson},
title = {Computers and Intractability: {A} Guide to the Theory of NP-Completeness},
publisher = {W. H. Freeman},
year = {1979}
}
@article{DBLP:journals/ior/GareyGJ78,
author = {M. R. Garey and
Ronald L. Graham and
David S. Johnson},
title = {Performance Guarantees for Scheduling Algorithms},
journal = {Oper. Res.},
volume = {26},
number = {1},
pages = {3--21},
year = {1978}
}
@article{DBLP:journals/ipl/GareyJPT78,
author = {M. R. Garey and
David S. Johnson and
Franco P. Preparata and
Robert Endre Tarjan},
title = {Triangulating a Simple Polygon},
journal = {Inf. Process. Lett.},
volume = {7},
number = {4},
pages = {175--179},
year = {1978}
}
@article{DBLP:journals/jacm/GareyJ78,
author = {M. R. Garey and
David S. Johnson},
title = {"Strong" NP-Completeness Results: Motivation, Examples,
and Implications},
journal = {J. {ACM}},
volume = {25},
number = {3},
pages = {499--508},
year = {1978}
}
@article{DBLP:journals/networks/BoyceGJ78,
author = {William M. Boyce and
M. R. Garey and
David S. Johnson},
title = {A note on bisecting minimum spanning trees},
journal = {Networks},
volume = {8},
number = {3},
pages = {187--192},
year = {1978}
}
@article{DBLP:journals/networks/JohnsonLK78,
author = {David S. Johnson and
Jan Karel Lenstra and
A. H. G. Rinnooy Kan},
title = {The complexity of the network design problem},
journal = {Networks},
volume = {8},
number = {4},
pages = {279--285},
year = {1978}
}
@article{DBLP:journals/siamcomp/CoffmanGJ78,
author = {Edward G. Coffman Jr. and
M. R. Garey and
David S. Johnson},
title = {An Application of Bin-Packing to Multiprocessor Scheduling},
journal = {{SIAM} J. Comput.},
volume = {7},
number = {1},
pages = {1--17},
year = {1978}
}
@article{DBLP:journals/sigact/GareyJ78,
author = {Michael R. Garey and
David S. Johnson},
title = {A note on "A note on 'Some simplified NP-complete graph problems'"},
journal = {{SIGACT} News},
volume = {9},
number = {4},
pages = {17},
year = {1978}
}
@article{DBLP:journals/tcs/JohnsonP78,
author = {David S. Johnson and
Franco P. Preparata},
title = {The Densest Hemisphere Problem},
journal = {Theor. Comput. Sci.},
volume = {6},
pages = {93--107},
year = {1978}
}
@inproceedings{DBLP:conf/focs/FraenkelGJSY78,
author = {Aviezri S. Fraenkel and
M. R. Garey and
David S. Johnson and
T. Schaefer and
Yaacov Yesha},
title = {The Complexity of Checkers on an {N} * {N} Board - Preliminary Report},
booktitle = {{FOCS}},
pages = {55--64},
publisher = {{IEEE} Computer Society},
year = {1978}
}
@article{DBLP:journals/mor/BruckerGJ77,
author = {Peter Brucker and
Michael R. Garey and
David S. Johnson},
title = {Scheduling Equal-Length Tasks Under Treelike Precedence Constraints
to Minimize Maximum Lateness},
journal = {Math. Oper. Res.},
volume = {2},
number = {3},
pages = {275--284},
year = {1977}
}
@article{DBLP:journals/siamam/GareyJ77,
author = {M. R. Garey and
David S. Johnson},
title = {The Rectilinear Steiner Tree Problem is {NP} Complete},
journal = {{SIAM} Journal of Applied Mathematics},
volume = {32},
pages = {826--834},
year = {1977}
}
@article{DBLP:journals/siamcomp/GareyJ77,
author = {M. R. Garey and
David S. Johnson},
title = {Two-Processor Scheduling with Start-Times and Deadlines},
journal = {{SIAM} J. Comput.},
volume = {6},
number = {3},
pages = {416--426},
year = {1977}
}
@article{DBLP:journals/tc/GareyHJ77,
author = {M. R. Garey and
Frank K. Hwang and
David S. Johnson},
title = {Algorithms for a Set Partitioning Problem Arising in the Design of
Multipurpose Units},
journal = {{IEEE} Trans. Computers},
volume = {26},
number = {4},
pages = {321--328},
year = {1977}
}
@article{DBLP:journals/jacm/GareyJ76a,
author = {M. R. Garey and
David S. Johnson},
title = {The Complexity of Near-Optimal Graph Coloring},
journal = {J. {ACM}},
volume = {23},
number = {1},
pages = {43--49},
year = {1976}
}
@article{DBLP:journals/jacm/GareyJ76b,
author = {M. R. Garey and
David S. Johnson},
title = {Scheduling Tasks with Nonuniform Deadlines on Two Processors},
journal = {J. {ACM}},
volume = {23},
number = {3},
pages = {461--467},
year = {1976}
}
@article{DBLP:journals/jct/GareyGJ76,
author = {M. R. Garey and
Ronald L. Graham and
David S. Johnson and
Andrew Chi{-}Chih Yao},
title = {Resource Constrained Scheduling as Generalized Bin Packing},
journal = {J. Comb. Theory, Ser. {A}},
volume = {21},
number = {3},
pages = {257--298},
year = {1976}
}
@article{DBLP:journals/mor/GareyJS76,
author = {Michael R. Garey and
David S. Johnson and
Ravi Sethi},
title = {The Complexity of Flowshop and Jobshop Scheduling},
journal = {Math. Oper. Res.},
volume = {1},
number = {2},
pages = {117--129},
year = {1976}
}
@article{DBLP:journals/siamcomp/GareyJT76,
author = {M. R. Garey and
David S. Johnson and
Robert Endre Tarjan},
title = {The Planar Hamiltonian Circuit Problem is NP-Complete},
journal = {{SIAM} J. Comput.},
volume = {5},
number = {4},
pages = {704--714},
year = {1976}
}
@article{DBLP:journals/tcs/GareyJS76,
author = {M. R. Garey and
David S. Johnson and
Larry J. Stockmeyer},
title = {Some Simplified NP-Complete Graph Problems},
journal = {Theor. Comput. Sci.},
volume = {1},
number = {3},
pages = {237--267},
year = {1976}
}
@inproceedings{DBLP:conf/stoc/GareyGJ76,
author = {M. R. Garey and
Ronald L. Graham and
David S. Johnson},
title = {Some NP-Complete Geometric Problems},
booktitle = {{STOC}},
pages = {10--22},
publisher = {{ACM}},
year = {1976}
}
@article{DBLP:journals/siamcomp/GareyJ75,
author = {M. R. Garey and
David S. Johnson},
title = {Complexity Results for Multiprocessor Scheduling under Resource Constraints},
journal = {{SIAM} J. Comput.},
volume = {4},
number = {4},
pages = {397--411},
year = {1975}
}
@inproceedings{DBLP:conf/focs/GareyJS75,
author = {M. R. Garey and
David S. Johnson and
H. C. So},
title = {An Application of Graph Coloring to Printed Circuit Testing (Working
Paper)},
booktitle = {{FOCS}},
pages = {178--183},
publisher = {{IEEE} Computer Society},
year = {1975}
}
@article{DBLP:journals/jcss/Johnson74,
author = {David S. Johnson},
title = {Fast Algorithms for Bin Packing},
journal = {J. Comput. Syst. Sci.},
volume = {8},
number = {3},
pages = {272--314},
year = {1974}
}
@article{DBLP:journals/jcss/Johnson74a,
author = {David S. Johnson},
title = {Approximation Algorithms for Combinatorial Problems},
journal = {J. Comput. Syst. Sci.},
volume = {9},
number = {3},
pages = {256--278},
year = {1974}
}
@article{DBLP:journals/siamcomp/JohnsonDUGG74,
author = {David S. Johnson and
Alan J. Demers and
Jeffrey D. Ullman and
M. R. Garey and
Ronald L. Graham},
title = {Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms},
journal = {{SIAM} J. Comput.},
volume = {3},
number = {4},
pages = {299--325},
year = {1974}
}
@inproceedings{DBLP:conf/stoc/GareyJS74,
author = {M. R. Garey and
David S. Johnson and
Larry J. Stockmeyer},
title = {Some Simplified NP-Complete Problems},
booktitle = {{STOC}},
pages = {47--63},
publisher = {{ACM}},
year = {1974}
}
@inproceedings{DBLP:conf/stoc/Johnson73,
author = {David S. Johnson},
title = {Approximation Algorithms for Combinatorial Problems},
booktitle = {{STOC}},
pages = {38--49},
publisher = {{ACM}},
year = {1973}
}
@inproceedings{DBLP:conf/focs/Johnson72,
author = {David S. Johnson},
title = {Fast Allocation Algorithms},
booktitle = {{SWAT}},
pages = {144--154},
publisher = {{IEEE} Computer Society},
year = {1972}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2023-10-01 22:34 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
