Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDavid S. Johnson
- > Home > Persons > David S. Johnson
Publications
- 2002
[j78]Edward G. Coffman Jr., Costas Courcoubetis, Michael R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis:
Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing. SIAM Rev. 44(1): 95-108 (2002)- 2000
- [j76]Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis:
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings. SIAM J. Discret. Math. 13(3): 384-402 (2000) - 1991
- [c16]Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis:
Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study. STOC 1991: 230-240 - 1988
- [j59]Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou:
The complexity of searching a graph. J. ACM 35(1): 18-44 (1988) - 1987
- [j54]Edward G. Coffman Jr., M. R. Garey, David S. Johnson:
Bin packing with divisible item sizes. J. Complex. 3(4): 406-428 (1987) - 1985
- [j47]David S. Johnson, M. R. Garey:
A 71/60 theorem for bin packing. J. Complex. 1(1): 65-106 (1985) - [j46]M. R. Garey, David S. Johnson:
Composing Functions to Minimize Image Size. SIAM J. Comput. 14(2): 500-503 (1985) - [j45]Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh:
Scheduling File Transfers. SIAM J. Comput. 14(3): 744-780 (1985) - 1983
- [j33]Edward G. Coffman Jr., M. R. Garey, David S. Johnson:
Dynamic Bin Packing. SIAM J. Comput. 12(2): 227-258 (1983) - [c10]Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh:
Scheduling File Transfers in a Distributed Network. PODC 1983: 254-266 - 1982
- [j27]M. R. Garey, David S. Johnson, Hans S. Witsenhausen:
The complexity of the generalized Lloyd - Max problem. IEEE Trans. Inf. Theory 28(2): 255-256 (1982) - 1981
- [j25]M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan:
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines. SIAM J. Comput. 10(2): 256-269 (1981) - [c7]Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou:
The Complexity of Searching a Graph (Preliminary Version). FOCS 1981: 376-385 - 1980
- [j24]Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan:
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM J. Comput. 9(4): 808-826 (1980) - [j23]M. R. Garey, David S. Johnson, Gerald L. Miller, Christos H. Papadimitriou:
The Complexity of Coloring Circular Arcs and Chords. SIAM J. Algebraic Discret. Methods 1(2): 216-227 (1980) - 1979
- [b1]M. R. Garey, David S. Johnson:
Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 - 1978
- [j22]M. R. Garey, Ronald L. Graham, David S. Johnson:
Performance Guarantees for Scheduling Algorithms. Oper. Res. 26(1): 3-21 (1978) - [j21]M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan:
Triangulating a Simple Polygon. Inf. Process. Lett. 7(4): 175-179 (1978) - [j20]M. R. Garey, David S. Johnson:
"Strong" NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25(3): 499-508 (1978) - [j19]William M. Boyce, M. R. Garey, David S. Johnson:
A note on bisecting minimum spanning trees. Networks 8(3): 187-192 (1978) - [j17]Edward G. Coffman Jr., M. R. Garey, David S. Johnson:
An Application of Bin-Packing to Multiprocessor Scheduling. SIAM J. Comput. 7(1): 1-17 (1978) - [j16]Michael R. Garey, David S. Johnson:
A note on "A note on 'Some simplified NP-complete graph problems'". SIGACT News 9(4): 17 (1978) - [c6]Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha:
The Complexity of Checkers on an N * N Board - Preliminary Report. FOCS 1978: 55-64 - 1977
- [j14]Peter Brucker, Michael R. Garey, David S. Johnson:
Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness. Math. Oper. Res. 2(3): 275-284 (1977) - [j13]M. R. Garey, David S. Johnson:
The Rectilinear Steiner Tree Problem is NP Complete. SIAM Journal of Applied Mathematics 32: 826-834 (1977) - [j12]M. R. Garey, David S. Johnson:
Two-Processor Scheduling with Start-Times and Deadlines. SIAM J. Comput. 6(3): 416-426 (1977) - [j11]M. R. Garey, Frank K. Hwang, David S. Johnson:
Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units. IEEE Trans. Computers 26(4): 321-328 (1977) - 1976
- [j10]M. R. Garey, David S. Johnson:
The Complexity of Near-Optimal Graph Coloring. J. ACM 23(1): 43-49 (1976) - [j9]M. R. Garey, David S. Johnson:
Scheduling Tasks with Nonuniform Deadlines on Two Processors. J. ACM 23(3): 461-467 (1976) - [j8]M. R. Garey, Ronald L. Graham, David S. Johnson, Andrew Chi-Chih Yao:
Resource Constrained Scheduling as Generalized Bin Packing. J. Comb. Theory, Ser. A 21(3): 257-298 (1976) - [j7]Michael R. Garey, David S. Johnson, Ravi Sethi:
The Complexity of Flowshop and Jobshop Scheduling. Math. Oper. Res. 1(2): 117-129 (1976) - [j6]M. R. Garey, David S. Johnson, Robert Endre Tarjan:
The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput. 5(4): 704-714 (1976) - [j5]M. R. Garey, David S. Johnson, Larry J. Stockmeyer:
Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267 (1976) - [c5]M. R. Garey, Ronald L. Graham, David S. Johnson:
Some NP-Complete Geometric Problems. STOC 1976: 10-22 - 1975
- [j4]M. R. Garey, David S. Johnson:
Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM J. Comput. 4(4): 397-411 (1975) - [c4]M. R. Garey, David S. Johnson, H. C. So:
An Application of Graph Coloring to Printed Circuit Testing (Working Paper). FOCS 1975: 178-183 - 1974
- [j1]David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham:
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM J. Comput. 3(4): 299-325 (1974) - [c3]M. R. Garey, David S. Johnson, Larry J. Stockmeyer:
Some Simplified NP-Complete Problems. STOC 1974: 47-63
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.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
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:
