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},
url = {https://doi.org/10.48550/arXiv.2306.08933},
doi = {10.48550/ARXIV.2306.08933},
eprinttype = {arXiv},
eprint = {2306.08933},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2306-08933.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {29th European Signal Processing Conference, {EUSIPCO} 2021, Dublin,
Ireland, August 23-27, 2021},
pages = {556--560},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.23919/EUSIPCO54536.2021.9616102},
doi = {10.23919/EUSIPCO54536.2021.9616102},
timestamp = {Thu, 09 Dec 2021 12:26:50 +0100},
biburl = {https://dblp.org/rec/conf/eusipco/JohnsonLTMGAL21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {Alex Orailoglu and
Matthias Jung and
Marc Reichenbach},
title = {SEC-Learn: Sensor Edge Cloud for Federated Learning - Invited Paper},
booktitle = {Embedded Computer Systems: Architectures, Modeling, and Simulation
- 21st International Conference, {SAMOS} 2021, Virtual Event, July
4-8, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13227},
pages = {432--448},
publisher = {Springer},
year = {2021},
url = {https://doi.org/10.1007/978-3-031-04580-6\_29},
doi = {10.1007/978-3-031-04580-6\_29},
timestamp = {Wed, 08 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/samos/AichrothAGGJJKK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://arxiv.org/abs/2102.08833},
eprinttype = {arXiv},
eprint = {2102.08833},
timestamp = {Fri, 19 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2102-08833.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1287/opre.2019.1956},
doi = {10.1287/OPRE.2019.1956},
timestamp = {Tue, 30 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ior/JohnsonBDDGHKRS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/j.tcs.2019.07.016},
doi = {10.1016/J.TCS.2019.07.016},
timestamp = {Mon, 24 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/GarayJKY20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {28th European Signal Processing Conference, {EUSIPCO} 2020, Amsterdam,
Netherlands, January 18-21, 2021},
pages = {81--85},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.23919/Eusipco47968.2020.9287327},
doi = {10.23919/EUSIPCO47968.2020.9287327},
timestamp = {Fri, 08 Jan 2021 16:18:38 +0100},
biburl = {https://dblp.org/rec/conf/eusipco/JohnsonG20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1007/s10878-018-0310-x},
doi = {10.1007/S10878-018-0310-X},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jco/EpsteinJL18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {Proceedings of the Nineteenth {ACM} International Symposium on Mobile
Ad Hoc Networking and Computing, MobiHoc 2018, Los Angeles, CA, USA,
June 26-29, 2018},
pages = {221--230},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3209582.3209605},
doi = {10.1145/3209582.3209605},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/mobihoc/ApplegateAJNTY18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {http://arxiv.org/abs/1805.06420},
eprinttype = {arXiv},
eprint = {1805.06420},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1805-06420.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/Johnson16,
author = {David S. Johnson},
title = {Bin Packing},
booktitle = {Encyclopedia of Algorithms},
pages = {207--211},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_49},
doi = {10.1007/978-1-4939-2864-4\_49},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/Johnson16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_181},
doi = {10.1007/978-1-4939-2864-4\_181},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/DemetrescuGJ16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/Johnson16a,
author = {David S. Johnson},
title = {Vector Bin Packing},
booktitle = {Encyclopedia of Algorithms},
pages = {2319--2323},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_495},
doi = {10.1007/978-1-4939-2864-4\_495},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/Johnson16a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {http://arxiv.org/abs/1611.01210},
eprinttype = {arXiv},
eprint = {1611.01210},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/JohnsonBDD0HKRS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.4230/DagRep.6.3.24},
doi = {10.4230/DAGREP.6.3.24},
timestamp = {Wed, 07 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dagstuhl-reports/DellingDJV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tcc/GarayGJKY15,
author = {Juan A. Garay and
Ran Gelles and
David S. Johnson and
Aggelos Kiayias and
Moti Yung},
editor = {Yevgeniy Dodis and
Jesper Buus Nielsen},
title = {A Little Honesty Goes a Long Way - The Two-Tier Model for Secure Multiparty
Computation},
booktitle = {Theory of Cryptography - 12th Theory of Cryptography Conference, {TCC}
2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {9014},
pages = {134--158},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-46494-6\_7},
doi = {10.1007/978-3-662-46494-6\_7},
timestamp = {Tue, 20 Aug 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tcc/GarayGJKY15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {http://eprint.iacr.org/2014/209},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/GarayGJKY14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/GarayJKY13,
author = {Juan A. Garay and
David S. Johnson and
Aggelos Kiayias and
Moti Yung},
editor = {Robert D. Kleinberg},
title = {Resource-based corruptions and the combinatorics of hidden diversity},
booktitle = {Innovations in Theoretical Computer Science, {ITCS} '13, Berkeley,
CA, USA, January 9-12, 2013},
pages = {415--428},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2422436.2422482},
doi = {10.1145/2422436.2422482},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/GarayJKY13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.4230/DagRep.3.9.169},
doi = {10.4230/DAGREP.3.9.169},
timestamp = {Wed, 07 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dagstuhl-reports/GoldbergIJW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {http://eprint.iacr.org/2012/556},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/GarayJKY12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {Matthias M{\"{u}}ller{-}Hannemann and
Renato Fonseca F. Werneck},
title = {Disjoint-Path Facility Location: Theory and Practice},
booktitle = {Proceedings of the Thirteenth Workshop on Algorithm Engineering and
Experiments, {ALENEX} 2011, Holiday Inn San Francisco Golden Gateway,
San Francisco, California, USA, January 22, 2011},
pages = {60--74},
publisher = {{SIAM}},
year = {2011},
url = {https://doi.org/10.1137/1.9781611972917.7},
doi = {10.1137/1.9781611972917.7},
timestamp = {Wed, 14 Nov 2018 10:52:08 +0100},
biburl = {https://dblp.org/rec/conf/alenex/BreslauDDGHJKRS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {http://drops.dagstuhl.de/portals/10261/},
timestamp = {Thu, 10 Jun 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/2010P10261.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/ItalianoJMS10,
author = {Giuseppe F. Italiano and
David S. Johnson and
Petra Mutzel and
Peter Sanders},
editor = {Giuseppe F. Italiano and
David S. Johnson and
Petra Mutzel and
Peter Sanders},
title = {10261 Abstracts Collection - Algorithm Engineering},
booktitle = {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},
url = {http://drops.dagstuhl.de/opus/volltexte/2010/2817/},
timestamp = {Thu, 10 Jun 2021 13:02:04 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/ItalianoJMS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/ItalianoJMS10a,
author = {Giuseppe F. Italiano and
David S. Johnson and
Petra Mutzel and
Peter Sanders},
editor = {Giuseppe F. Italiano and
David S. Johnson and
Petra Mutzel and
Peter Sanders},
title = {10261 Executive Summary - Algorithm Engineering},
booktitle = {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},
url = {http://drops.dagstuhl.de/opus/volltexte/2010/2796/},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/ItalianoJMS10a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1090/dimacs/074},
doi = {10.1090/DIMACS/074},
isbn = {978-0-8218-4383-3},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/dimacs74.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/j.dam.2007.10.007},
doi = {10.1016/J.DAM.2007.10.007},
timestamp = {Fri, 09 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dam/JohnsonMT08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/DemetrescuGJ08,
author = {Camil Demetrescu and
Andrew V. Goldberg and
David S. Johnson},
editor = {Ming{-}Yang Kao},
title = {Implementation Challenge for Shortest Paths},
booktitle = {Encyclopedia of Algorithms - 2008 Edition},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-0-387-30162-4\_181},
doi = {10.1007/978-0-387-30162-4\_181},
timestamp = {Thu, 27 Jun 2019 16:25:31 +0200},
biburl = {https://dblp.org/rec/reference/algo/DemetrescuGJ08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/Johnson08,
author = {David S. Johnson},
editor = {Ming{-}Yang Kao},
title = {Bin Packing},
booktitle = {Encyclopedia of Algorithms - 2008 Edition},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-0-387-30162-4\_49},
doi = {10.1007/978-0-387-30162-4\_49},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/Johnson08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/1240233.1240247},
doi = {10.1145/1240233.1240247},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/Johnson07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/expcs/Johnson07,
author = {David S. Johnson},
title = {What is the science in experimental computer science?},
booktitle = {Proceedings of the Workshop on Experimental Computer Science, Part
of {ACM} FCRC, San Diego, CA, USA, 13-14 June 2007},
pages = {1},
publisher = {{ACM}},
year = {2007},
url = {https://doi.org/10.1145/1281700.1281701},
doi = {10.1145/1281700.1281701},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/expcs/Johnson07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {Nikhil Bansal and
Kirk Pruhs and
Clifford Stein},
title = {Compressing rectilinear pictures and minimizing access control lists},
booktitle = {Proceedings of the Eighteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2007, New Orleans, Louisiana, USA, January 7-9,
2007},
pages = {1066--1075},
publisher = {{SIAM}},
year = {2007},
url = {http://dl.acm.org/citation.cfm?id=1283383.1283498},
timestamp = {Tue, 15 Feb 2022 07:54:27 +0100},
biburl = {https://dblp.org/rec/conf/soda/ApplegateCJKLW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
isbn = {978-1-59593-631-8},
timestamp = {Wed, 13 Jun 2007 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/2007.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/1120582.1120583},
doi = {10.1145/1120582.1120583},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/CsirikJKOSW06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/1159892.1159901},
doi = {10.1145/1159892.1159901},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/Johnson06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/1077464.1077476},
doi = {10.1145/1077464.1077476},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/Johnson05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1109/TVCG.2005.17},
doi = {10.1109/TVCG.2005.17},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tvcg/ChhuganiPKCVJK05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {http://arxiv.org/abs/cs/0509031},
eprinttype = {arXiv},
eprint = {cs/0509031},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0509031.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/vldb/JohnsonKCKV04,
author = {David S. Johnson and
Shankar Krishnan and
Jatin Chhugani and
Subodh Kumar and
Suresh Venkatasubramanian},
editor = {Mario A. Nascimento and
M. Tamer {\"{O}}zsu and
Donald Kossmann and
Ren{\'{e}}e J. Miller and
Jos{\'{e}} A. Blakeley and
K. Bernhard Schiefer},
title = {Compressing Large Boolean Matrices using Reordering Techniques},
booktitle = {(e)Proceedings of the Thirtieth International Conference on Very Large
Data Bases, {VLDB} 2004, Toronto, Canada, August 31 - September 3
2004},
pages = {13--23},
publisher = {Morgan Kaufmann},
year = {2004},
url = {http://www.vldb.org/conf/2004/RS1P1.PDF},
doi = {10.1016/B978-012088469-8.50005-X},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/vldb/JohnsonKCKV04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/876638.876640},
doi = {10.1145/876638.876640},
timestamp = {Sat, 05 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/BarvinokFJTWW03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {Richard E. Ladner},
title = {The Cutting-Stock Approach to Bin Packing: Theory and Experiments},
booktitle = {Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments,
Baltimore, MD, USA, January 11, 2003},
pages = {1--15},
publisher = {{SIAM}},
year = {2003},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/alenex/ApplegateBDJS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/S0036144501395423},
doi = {10.1137/S0036144501395423},
timestamp = {Tue, 29 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamrev/CoffmanCGJSWY02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1090/dimacs/059},
doi = {10.1090/DIMACS/059},
isbn = {978-0-8218-2892-2},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/dimacs59.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://arxiv.org/abs/cs/0204024},
timestamp = {Sat, 23 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-DS-0204024.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://arxiv.org/abs/cs/0210013},
timestamp = {Fri, 10 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/cs-DS-0210013.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1007/s00453-001-0041-7},
doi = {10.1007/S00453-001-0041-7},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/CsirikJ01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/alenex/CirasellaJMZ01,
author = {Jill Cirasella and
David S. Johnson and
Lyle A. McGeoch and
Weixiong Zhang},
editor = {Adam L. Buchsbaum and
Jack Snoeyink},
title = {The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators,
and Tests},
booktitle = {Algorithm Engineering and Experimentation, Third International Workshop,
{ALENEX} 2001, Washington, DC, USA, January 5-6, 2001, Revised Papers},
series = {Lecture Notes in Computer Science},
volume = {2153},
pages = {32--59},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-44808-X\_3},
doi = {10.1007/3-540-44808-X\_3},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/alenex/CirasellaJMZ01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CsirikJK01,
author = {J{\'{a}}nos Csirik and
David S. Johnson and
Claire Kenyon},
editor = {S. Rao Kosaraju},
title = {Better approximation algorithms for bin covering},
booktitle = {Proceedings of the Twelfth Annual Symposium on Discrete Algorithms,
January 7-9, 2001, Washington, DC, {USA}},
pages = {557--566},
publisher = {{ACM/SIAM}},
year = {2001},
url = {http://dl.acm.org/citation.cfm?id=365411.365533},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/CsirikJK01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/S0895480197325936},
doi = {10.1137/S0895480197325936},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/CoffmanCGJSWY00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JohnsonMP00,
author = {David S. Johnson and
Maria Minkoff and
Steven Phillips},
editor = {David B. Shmoys},
title = {The prize collecting Steiner tree problem: theory and practice},
booktitle = {Proceedings of the Eleventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, January 9-11, 2000, San Francisco, CA, {USA}},
pages = {760--769},
publisher = {{ACM/SIAM}},
year = {2000},
url = {http://dl.acm.org/citation.cfm?id=338219.338637},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/JohnsonMP00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {F. Frances Yao and
Eugene M. Luks},
title = {On the sum-of-squares algorithm for bin packing},
booktitle = {Proceedings of the Thirty-Second Annual {ACM} Symposium on Theory
of Computing, May 21-23, 2000, Portland, OR, {USA}},
pages = {208--217},
publisher = {{ACM}},
year = {2000},
url = {https://doi.org/10.1145/335305.335331},
doi = {10.1145/335305.335331},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CsirikJKOSW00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {Michael T. Goodrich and
Catherine C. McGeoch},
title = {A Self Organizing Bin Packing Heuristic},
booktitle = {Algorithm Engineering and Experimentation, International Workshop
{ALENEX} '99, Baltimore, MD, USA, January 15-16, 1999, Selected Papers},
series = {Lecture Notes in Computer Science},
volume = {1619},
pages = {246--265},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/3-540-48518-X\_15},
doi = {10.1007/3-540-48518-X\_15},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/alenex/CsirikJKSW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/Johnson99,
author = {David S. Johnson},
editor = {Michael H. Goldwasser and
David S. Johnson and
Catherine C. McGeoch},
title = {A theoretician's guide to the experimental analysis of algorithms},
booktitle = {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},
pages = {215--250},
publisher = {{DIMACS/AMS}},
year = {1999},
url = {https://doi.org/10.1090/dimacs/059/11},
doi = {10.1090/DIMACS/059/11},
timestamp = {Mon, 22 May 2023 16:07:34 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/Johnson99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JohnsonS99,
author = {David S. Johnson and
Mario Szegedy},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {What are the Least Tractable Instances of max Independent Set?},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {927--928},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.315093},
timestamp = {Tue, 01 Mar 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/JohnsonS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/BarvinokJWW98,
author = {Alexander I. Barvinok and
David S. Johnson and
Gerhard J. Woeginger and
Russell Woodroofe},
editor = {Robert E. Bixby and
E. Andrew Boyd and
Roger Z. R{\'{\i}}os{-}Mercado},
title = {The Maximum Traveling Salesman Problem Under Polyhedral Norms},
booktitle = {Integer Programming and Combinatorial Optimization, 6th International
{IPCO} Conference, Houston, Texas, USA, June 22-24, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1412},
pages = {195--201},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/3-540-69346-7\_15},
doi = {10.1007/3-540-69346-7\_15},
timestamp = {Sat, 05 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/ipco/BarvinokJWW98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1002/(SICI)1098-2418(199701/03)10:1/2\&\#60;69::AID-RSA4\&\#62;3.0.CO;2-V},
doi = {10.1002/(SICI)1098-2418(199701/03)10:1/2\&\#60;69::AID-RSA4\&\#62;3.0.CO;2-V},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/CoffmanJSW97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/262301.262309},
doi = {10.1145/262301.262309},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/AhoJKKMPP97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/262301.262310},
doi = {10.1145/262301.262310},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/sigact/CondonFFGJLMRSSS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pldi/YoungJKS97,
author = {Cliff Young and
David S. Johnson and
David R. Karger and
Michael D. Smith},
editor = {Marina C. Chen and
Ron K. Cytron and
A. Michael Berman},
title = {Near-optimal Intraprocedural Branch Alignment},
booktitle = {Proceedings of the {ACM} {SIGPLAN} '97 Conference on Programming Language
Design and Implementation (PLDI), Las Vegas, Nevada, USA, June 15-18,
1997},
pages = {183--193},
publisher = {{ACM}},
year = {1997},
url = {https://doi.org/10.1145/258915.258932},
doi = {10.1145/258915.258932},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/pldi/YoungJKS97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/235767.235771},
doi = {10.1145/235767.235771},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/Johnson96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/235666.571628},
doi = {10.1145/235666.571628},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/Johnson96a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JohnsonMR96,
author = {David S. Johnson and
Lyle A. McGeoch and
Edward E. Rothberg},
editor = {{\'{E}}va Tardos},
title = {Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman
Bound},
booktitle = {Proceedings of the Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, 28-30 January 1996, Atlanta, Georgia, {USA}},
pages = {341--350},
publisher = {{ACM/SIAM}},
year = {1996},
url = {http://dl.acm.org/citation.cfm?id=313852.314081},
timestamp = {Thu, 05 Jul 2018 07:29:31 +0200},
biburl = {https://dblp.org/rec/conf/soda/JohnsonMR96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1090/dimacs/026},
doi = {10.1090/DIMACS/026},
isbn = {978-0-8218-6609-2},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/dimacs26.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1006/jagm.1995.1018},
doi = {10.1006/JAGM.1995.1018},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/FredmanJMO95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/S0097539792225297},
doi = {10.1137/S0097539792225297},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/DahlhausJPSY94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ifip/Johnson94,
author = {David S. Johnson},
editor = {Bj{\"{o}}rn Pehrson and
Imre Simon},
title = {The Traveling Salesman Problem: {A} report on the State of the Art},
booktitle = {Technology and Foundations - Information Processing '94, Volume 1,
Proceedings of the {IFIP} 13th World Computer Congress, Hamburg, Germany,
28 August - 2 September, 1994},
series = {{IFIP} Transactions},
volume = {{A-51}},
pages = {221--222},
publisher = {North-Holland},
year = {1994},
timestamp = {Tue, 15 Mar 2016 13:03:03 +0100},
biburl = {https://dblp.org/rec/conf/ifip/Johnson94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {The 5th {IEEE} International Symposium on Personal, Indoor and Mobile
Radio Communications, {PIMRC} 1994, The Hague, The Netherlands, September
18-23, 1994},
pages = {1114--1120},
year = {1994},
url = {https://doi.org/10.1109/WNCMF.1994.529427},
doi = {10.1109/WNCMF.1994.529427},
timestamp = {Mon, 08 Jun 2020 16:35:56 +0200},
biburl = {https://dblp.org/rec/conf/pimrc/HaasWJ94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/JohnsonLP94,
author = {David S. Johnson and
Andrea S. LaPaugh and
Ron Y. Pinter},
editor = {Daniel Dominic Sleator},
title = {Minimizing Channel Density by Lateral Shifting of Components},
booktitle = {Proceedings of the Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms.
23-25 January 1994, Arlington, Virginia, {USA}},
pages = {122--131},
publisher = {{ACM/SIAM}},
year = {1994},
url = {http://dl.acm.org/citation.cfm?id=314464.314486},
timestamp = {Thu, 05 Jul 2018 07:29:19 +0200},
biburl = {https://dblp.org/rec/conf/soda/JohnsonLP94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1006/jpdc.1993.1069},
doi = {10.1006/JPDC.1993.1069},
timestamp = {Sat, 22 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jpdc/JohnsonB93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/JohnsonT93,
author = {David S. Johnson and
Michael A. Trick},
editor = {David S. Johnson and
Michael A. Trick},
title = {Foreword xiIntroduction to the Second {DIMACS} Challenge: Cliques,
coloring, and satisfiability},
booktitle = {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},
pages = {1--7},
publisher = {{DIMACS/AMS}},
year = {1993},
url = {https://doi.org/10.1090/dimacs/026/01},
doi = {10.1090/DIMACS/026/01},
timestamp = {Mon, 22 May 2023 16:07:35 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/JohnsonT93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/FredmanJMO93,
author = {Michael L. Fredman and
David S. Johnson and
Lyle A. McGeoch and
G. Ostheimer},
editor = {Vijaya Ramachandran},
title = {Data Structures for Traveling Salesmen},
booktitle = {Proceedings of the Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete
Algorithms, 25-27 January 1993, Austin, Texas, {USA}},
pages = {145--154},
publisher = {{ACM/SIAM}},
year = {1993},
url = {http://dl.acm.org/citation.cfm?id=313559.313668},
timestamp = {Thu, 05 Jul 2018 07:29:11 +0200},
biburl = {https://dblp.org/rec/conf/soda/FredmanJMO93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CoffmanJSW93,
author = {Edward G. Coffman Jr. and
David S. Johnson and
Peter W. Shor and
Richard R. Weber},
editor = {S. Rao Kosaraju and
David S. Johnson and
Alok Aggarwal},
title = {Markov chains, computer proofs, and average-case analysis of best
fit bin packing},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM} Symposium on Theory of
Computing, May 16-18, 1993, San Diego, CA, {USA}},
pages = {412--421},
publisher = {{ACM}},
year = {1993},
url = {https://doi.org/10.1145/167088.167203},
doi = {10.1145/167088.167203},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CoffmanJSW93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1090/dimacs/012},
doi = {10.1090/DIMACS/012},
isbn = {978-0-8218-6598-9},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/dimacs12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
isbn = {0-89791-591-7},
timestamp = {Mon, 17 Oct 2011 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/STOC25.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(92)90052-E},
doi = {10.1016/0196-6774(92)90052-E},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/DahlhausJPSY92,
author = {Elias Dahlhaus and
David S. Johnson and
Christos H. Papadimitriou and
Paul D. Seymour and
Mihalis Yannakakis},
editor = {S. Rao Kosaraju and
Mike Fellows and
Avi Wigderson and
John A. Ellis},
title = {The Complexity of Multiway Cuts (Extended Abstract)},
booktitle = {Proceedings of the 24th Annual {ACM} Symposium on Theory of Computing,
May 4-6, 1992, Victoria, British Columbia, Canada},
pages = {241--251},
publisher = {{ACM}},
year = {1992},
url = {https://doi.org/10.1145/129712.129736},
doi = {10.1145/129712.129736},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/DahlhausJPSY92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1287/opre.39.3.378},
doi = {10.1287/OPRE.39.3.378},
timestamp = {Tue, 31 Mar 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ior/JohnsonAMS91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/Johnson91,
author = {David S. Johnson},
editor = {David S. Johnson and
Catherine C. McGeoch},
title = {Appendix {B:} Panel Discussion Highlights},
booktitle = {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},
pages = {583--592},
publisher = {{DIMACS/AMS}},
year = {1991},
url = {https://doi.org/10.1090/dimacs/012/24},
doi = {10.1090/DIMACS/012/24},
timestamp = {Mon, 22 May 2023 16:07:35 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/Johnson91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/JohnsonM91,
author = {David S. Johnson and
Catherine C. McGeoch},
editor = {David S. Johnson and
Catherine C. McGeoch},
title = {Preface},
booktitle = {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},
pages = {xi},
publisher = {{DIMACS/AMS}},
year = {1991},
timestamp = {Fri, 15 Jan 2016 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/dimacs/JohnsonM91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CsirikJ91,
author = {J{\'{a}}nos Csirik and
David S. Johnson},
editor = {Alok Aggarwal},
title = {Bounded Space On-Line Bin Packing: Best is Better than First},
booktitle = {Proceedings of the Second Annual {ACM/SIGACT-SIAM} Symposium on Discrete
Algorithms, 28-30 January 1991, San Francisco, California, {USA}},
pages = {309--319},
publisher = {{ACM/SIAM}},
year = {1991},
url = {http://dl.acm.org/citation.cfm?id=127787.127846},
timestamp = {Thu, 05 Jul 2018 07:28:55 +0200},
biburl = {https://dblp.org/rec/conf/soda/CsirikJ91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {Cris Koutsougeras and
Jeffrey Scott Vitter},
title = {Fundamental Discrepancies between Average-Case Analyses under Discrete
and Continuous Distributions: {A} Bin Packing Case Study},
booktitle = {Proceedings of the 23rd Annual {ACM} Symposium on Theory of Computing,
May 5-8, 1991, New Orleans, Louisiana, {USA}},
pages = {230--240},
publisher = {{ACM}},
year = {1991},
url = {https://doi.org/10.1145/103418.103446},
doi = {10.1145/103418.103446},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CoffmanCGJMSWY91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0012-365X(90)90358-O},
doi = {10.1016/0012-365X(90)90358-O},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dm/ClarkCJ90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(90)90035-D},
doi = {10.1016/0196-6774(90)90035-D},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(90)90001-U},
doi = {10.1016/0196-6774(90)90001-U},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/BermanJLSS90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/379172.379173},
doi = {10.1145/379172.379173},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/Johnson90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Johnson90,
author = {David S. Johnson},
editor = {Mike Paterson},
title = {Local Optimization and the Traveling Salesman Problem},
booktitle = {Automata, Languages and Programming, 17th International Colloquium,
ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {443},
pages = {446--461},
publisher = {Springer},
year = {1990},
url = {https://doi.org/10.1007/BFb0032050},
doi = {10.1007/BFB0032050},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/Johnson90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/swat/Johnson90,
author = {David S. Johnson},
editor = {John R. Gilbert and
Rolf G. Karlsson},
title = {Data Structures for Traveling Salesmen (Abstract)},
booktitle = {{SWAT} 90, 2nd Scandinavian Workshop on Algorithm Theory, Bergen,
Norway, July 11-14, 1990, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {447},
pages = {287},
publisher = {Springer},
year = {1990},
url = {https://doi.org/10.1007/3-540-52846-6\_97},
doi = {10.1007/3-540-52846-6\_97},
timestamp = {Tue, 14 May 2019 10:00:39 +0200},
biburl = {https://dblp.org/rec/conf/swat/Johnson90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:books/el/leeuwen90/Johnson90,
author = {David S. Johnson},
editor = {Jan van Leeuwen},
title = {A Catalog of Complexity Classes},
booktitle = {Handbook of Theoretical Computer Science, Volume {A:} Algorithms and
Complexity},
pages = {67--161},
publisher = {Elsevier and {MIT} Press},
year = {1990},
timestamp = {Sat, 03 Aug 2019 19:26:43 +0200},
biburl = {https://dblp.org/rec/books/el/leeuwen90/Johnson90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {http://dl.acm.org/citation.cfm?id=320176},
isbn = {0-89871-251-3},
timestamp = {Thu, 05 Jul 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/1990.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1287/opre.37.6.865},
doi = {10.1287/OPRE.37.6.865},
timestamp = {Tue, 31 Mar 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ior/JohnsonAMS89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {{IEEE} International Conference on Acoustics, Speech, and Signal Processing,
{ICASSP} '89, Glasgow, Scotland, May 23-26, 1989},
pages = {2421--2424},
publisher = {{IEEE}},
year = {1989},
url = {https://doi.org/10.1109/ICASSP.1989.266956},
doi = {10.1109/ICASSP.1989.266956},
timestamp = {Mon, 09 Aug 2021 14:54:02 +0200},
biburl = {https://dblp.org/rec/conf/icassp/JaffeJLH89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
isbn = {0-89791-307-8},
timestamp = {Wed, 24 Nov 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/STOC21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0020-0190(88)90065-8},
doi = {10.1016/0020-0190(88)90065-8},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/JohnsonP88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/42267.42268},
doi = {10.1145/42267.42268},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/MegiddoHGJP88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(88)90033-8},
doi = {10.1016/0196-6774(88)90033-8},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0022-0000(88)90046-3},
doi = {10.1016/0022-0000(88)90046-3},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/JohnsonPY88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(87)90043-5},
doi = {10.1016/0196-6774(87)90043-5},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(87)90021-6},
doi = {10.1016/0196-6774(87)90021-6},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson87a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0885-064X(87)90009-4},
doi = {10.1016/0885-064X(87)90009-4},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jc/CoffmanGJ87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1002/jgt.3190110306},
doi = {10.1002/JGT.3190110306},
timestamp = {Fri, 02 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jgt/JohnsonP87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(86)90011-8},
doi = {10.1016/0196-6774(86)90011-8},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(86)90020-9},
doi = {10.1016/0196-6774(86)90020-9},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson86a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(85)90025-2},
doi = {10.1016/0196-6774(85)90025-2},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(85)90046-X},
doi = {10.1016/0196-6774(85)90046-X},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson85a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(85)90012-4},
doi = {10.1016/0196-6774(85)90012-4},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jal/Johnson85b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0885-064X(85)90022-6},
doi = {10.1016/0885-064X(85)90022-6},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jc/JohnsonG85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0214037},
doi = {10.1137/0214037},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GareyJ85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0214054},
doi = {10.1137/0214054},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CoffmanGJL85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {26th Annual Symposium on Foundations of Computer Science, Portland,
Oregon, USA, 21-23 October 1985},
pages = {39--42},
publisher = {{IEEE} Computer Society},
year = {1985},
url = {https://doi.org/10.1109/SFCS.1985.31},
doi = {10.1109/SFCS.1985.31},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JohnsonPY85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(84)90045-2},
doi = {10.1016/0196-6774(84)90045-2},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(84)90032-4},
doi = {10.1016/0196-6774(84)90032-4},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson84a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(84)90022-1},
doi = {10.1016/0196-6774(84)90022-1},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson84b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(84)90004-X},
doi = {10.1016/0196-6774(84)90004-X},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/AssmannJKL84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(84)90010-5},
doi = {10.1016/0196-6774(84)90010-5},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson84c.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0022-0000(84)90081-3},
doi = {10.1016/0022-0000(84)90081-3},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcss/JohnsonK84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/1008959.1008960},
doi = {10.1145/1008959.1008960},
timestamp = {Sat, 31 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/sigact/Johnson84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
editor = {Richard A. DeMillo},
title = {Some Unexpected Expected Behavior Results for Bin Packing},
booktitle = {Proceedings of the 16th Annual {ACM} Symposium on Theory of Computing,
April 30 - May 2, 1984, Washington, DC, {USA}},
pages = {279--288},
publisher = {{ACM}},
year = {1984},
url = {https://doi.org/10.1145/800057.808692},
doi = {10.1145/800057.808692},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BentleyJLMM84.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(83)90038-X},
doi = {10.1016/0196-6774(83)90038-X},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson83.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(83)90045-7},
doi = {10.1016/0196-6774(83)90045-7},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson83a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(83)90028-7},
doi = {10.1016/0196-6774(83)90028-7},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson83b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(83)90019-6},
doi = {10.1016/0196-6774(83)90019-6},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson83c.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0212014},
doi = {10.1137/0212014},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CoffmanGJ83.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0212042},
doi = {10.1137/0212042},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/JohnsonK83.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/podc/CoffmanGJL83,
author = {Edward G. Coffman Jr. and
M. R. Garey and
David S. Johnson and
Andrea S. LaPaugh},
editor = {Robert L. Probert and
Nancy A. Lynch and
Nicola Santoro},
title = {Scheduling File Transfers in a Distributed Network},
booktitle = {Proceedings of the Second Annual {ACM} Symposium on Principles of
Distributed Computing, Montreal, Quebec, Canada, August 17-19, 1983},
pages = {254--266},
publisher = {{ACM}},
year = {1983},
url = {https://doi.org/10.1145/800221.806726},
doi = {10.1145/800221.806726},
timestamp = {Thu, 02 Feb 2023 12:03:21 +0100},
biburl = {https://dblp.org/rec/conf/podc/CoffmanGJL83.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
timestamp = {Mon, 17 Oct 2011 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/STOC15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(82)90011-6},
doi = {10.1016/0196-6774(82)90011-6},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson82c.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(82)90018-9},
doi = {10.1016/0196-6774(82)90018-9},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson82.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(82)90026-8},
doi = {10.1016/0196-6774(82)90026-8},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson82a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(82)90032-3},
doi = {10.1016/0196-6774(82)90032-3},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson82b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1109/TIT.1982.1056488},
doi = {10.1109/TIT.1982.1056488},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/GareyJW82.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/JohnsonK82,
author = {David S. Johnson and
Anthony C. Klug},
editor = {Jeffrey D. Ullman and
Alfred V. Aho},
title = {Testing Containment of Conjunctive Queries Under Functional and Inclusion
Dependencies},
booktitle = {Proceedings of the {ACM} Symposium on Principles of Database Systems,
March 29-31, 1982, Los Angeles, California, {USA}},
pages = {164--169},
publisher = {{ACM}},
year = {1982},
url = {https://doi.org/10.1145/588111.588138},
doi = {10.1145/588111.588138},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/pods/JohnsonK82.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0196-6774(81)90037-7},
doi = {10.1016/0196-6774(81)90037-7},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jal/Johnson81.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0210018},
doi = {10.1137/0210018},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GareyJST81.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {22nd Annual Symposium on Foundations of Computer Science, Nashville,
Tennessee, USA, 28-30 October 1981},
pages = {203--211},
publisher = {{IEEE} Computer Society},
year = {1981},
url = {https://doi.org/10.1109/SFCS.1981.33},
doi = {10.1109/SFCS.1981.33},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/JohnsonK81.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {22nd Annual Symposium on Foundations of Computer Science, Nashville,
Tennessee, USA, 28-30 October 1981},
pages = {376--385},
publisher = {{IEEE} Computer Society},
year = {1981},
url = {https://doi.org/10.1109/SFCS.1981.46},
doi = {10.1109/SFCS.1981.46},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/MegiddoHGJP81.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0209062},
doi = {10.1137/0209062},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CoffmanGJT80.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0601025},
doi = {10.1137/0601025},
timestamp = {Fri, 01 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siammax/GareyJMP80.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
isbn = {0-7167-1044-7},
timestamp = {Thu, 29 Mar 2007 01:00:00 +0200},
biburl = {https://dblp.org/rec/books/fm/GareyJ79.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1287/opre.26.1.3},
doi = {10.1287/OPRE.26.1.3},
timestamp = {Tue, 31 Mar 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ior/GareyGJ78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0020-0190(78)90062-5},
doi = {10.1016/0020-0190(78)90062-5},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/GareyJPT78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/322077.322090},
doi = {10.1145/322077.322090},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/GareyJ78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1002/net.3230080302},
doi = {10.1002/NET.3230080302},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/networks/BoyceGJ78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1002/net.3230080402},
doi = {10.1002/NET.3230080402},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/networks/JohnsonLK78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0207001},
doi = {10.1137/0207001},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CoffmanGJ78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/1008369.1008371},
doi = {10.1145/1008369.1008371},
timestamp = {Tue, 03 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/sigact/GareyJ78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0304-3975(78)90006-3},
doi = {10.1016/0304-3975(78)90006-3},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/JohnsonP78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {19th Annual Symposium on Foundations of Computer Science, Ann Arbor,
Michigan, USA, 16-18 October 1978},
pages = {55--64},
publisher = {{IEEE} Computer Society},
year = {1978},
url = {https://doi.org/10.1109/SFCS.1978.36},
doi = {10.1109/SFCS.1978.36},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/FraenkelGJSY78.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1287/moor.2.3.275},
doi = {10.1287/MOOR.2.3.275},
timestamp = {Sun, 28 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mor/BruckerGJ77.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
timestamp = {Thu, 25 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamam/GareyJ77.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0206029},
doi = {10.1137/0206029},
timestamp = {Sat, 30 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GareyJ77.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1109/TC.1977.1674841},
doi = {10.1109/TC.1977.1674841},
timestamp = {Sat, 20 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tc/GareyHJ77.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/321921.321926},
doi = {10.1145/321921.321926},
timestamp = {Sat, 30 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/GareyJ76a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1145/321958.321967},
doi = {10.1145/321958.321967},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/GareyJ76b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0097-3165(76)90001-7},
doi = {10.1016/0097-3165(76)90001-7},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jct/GareyGJ76.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1287/moor.1.2.117},
doi = {10.1287/MOOR.1.2.117},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mor/GareyJS76.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0205049},
doi = {10.1137/0205049},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GareyJT76.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/0304-3975(76)90059-1},
doi = {10.1016/0304-3975(76)90059-1},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/GareyJS76.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GareyGJ76,
author = {M. R. Garey and
Ronald L. Graham and
David S. Johnson},
editor = {Ashok K. Chandra and
Detlef Wotschke and
Emily P. Friedman and
Michael A. Harrison},
title = {Some NP-Complete Geometric Problems},
booktitle = {Proceedings of the 8th Annual {ACM} Symposium on Theory of Computing,
May 3-5, 1976, Hershey, Pennsylvania, {USA}},
pages = {10--22},
publisher = {{ACM}},
year = {1976},
url = {https://doi.org/10.1145/800113.803626},
doi = {10.1145/800113.803626},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GareyGJ76.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0204035},
doi = {10.1137/0204035},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GareyJ75.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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 = {16th Annual Symposium on Foundations of Computer Science, Berkeley,
California, USA, October 13-15, 1975},
pages = {178--183},
publisher = {{IEEE} Computer Society},
year = {1975},
url = {https://doi.org/10.1109/SFCS.1975.3},
doi = {10.1109/SFCS.1975.3},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GareyJS75.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/S0022-0000(74)80026-7},
doi = {10.1016/S0022-0000(74)80026-7},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Johnson74.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1016/S0022-0000(74)80044-9},
doi = {10.1016/S0022-0000(74)80044-9},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Johnson74a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@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},
url = {https://doi.org/10.1137/0203025},
doi = {10.1137/0203025},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/JohnsonDUGG74.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GareyJS74,
author = {M. R. Garey and
David S. Johnson and
Larry J. Stockmeyer},
editor = {Robert L. Constable and
Robert W. Ritchie and
Jack W. Carlyle and
Michael A. Harrison},
title = {Some Simplified NP-Complete Problems},
booktitle = {Proceedings of the 6th Annual {ACM} Symposium on Theory of Computing,
April 30 - May 2, 1974, Seattle, Washington, {USA}},
pages = {47--63},
publisher = {{ACM}},
year = {1974},
url = {https://doi.org/10.1145/800119.803884},
doi = {10.1145/800119.803884},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GareyJS74.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Johnson73,
author = {David S. Johnson},
editor = {Alfred V. Aho and
Allan Borodin and
Robert L. Constable and
Robert W. Floyd and
Michael A. Harrison and
Richard M. Karp and
H. Raymond Strong},
title = {Approximation Algorithms for Combinatorial Problems},
booktitle = {Proceedings of the 5th Annual {ACM} Symposium on Theory of Computing,
April 30 - May 2, 1973, Austin, Texas, {USA}},
pages = {38--49},
publisher = {{ACM}},
year = {1973},
url = {https://doi.org/10.1145/800125.804034},
doi = {10.1145/800125.804034},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Johnson73.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Johnson72,
author = {David S. Johnson},
title = {Fast Allocation Algorithms},
booktitle = {13th Annual Symposium on Switching and Automata Theory, College Park,
Maryland, USA, October 25-27, 1972},
pages = {144--154},
publisher = {{IEEE} Computer Society},
year = {1972},
url = {https://doi.org/10.1109/SWAT.1972.4},
doi = {10.1109/SWAT.1972.4},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Johnson72.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
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:
