default search action
M. R. Garey
Person information
- affiliation: Bell Labs
- award (1979): Frederick W. Lanchester Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2000 – 2009
- 2002
- [j50]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
- [j49]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)
1990 – 1999
- 1993
- [j48]Edward G. Coffman Jr., M. R. Garey:
Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling. J. ACM 40(5): 991-1018 (1993) - 1991
- [c11]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 - [c10]Edward G. Coffman Jr., M. R. Garey:
Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling. STOC 1991: 241-248
1980 – 1989
- 1989
- [c9]Sudhir Aggarwal, Daniel Barbará, Walter Cunto, M. R. Garey:
The Complexity of Collapsing Reachability Graphs. Automatic Verification Methods for Finite State Systems 1989: 264-274 - 1988
- [j47]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) - [j46]Michael R. Garey, Robert E. Tarjan, Gordon T. Wilfong:
One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties. Math. Oper. Res. 13(2): 330-348 (1988) - [j45]Fan R. K. Chung, Zoltán Füredi, M. R. Garey, Ronald L. Graham:
On the Fractional Covering Number of Hypergraphs. SIAM J. Discret. Math. 1(1): 45-49 (1988) - [j44]Michael R. Garey, Frank K. Hwang, Gaylord W. Richards:
Asymptotic results for partial concentrators. IEEE Trans. Commun. 36(2): 214-217 (1988) - 1987
- [j43]Edward G. Coffman Jr., M. R. Garey, David S. Johnson:
Bin packing with divisible item sizes. J. Complex. 3(4): 406-428 (1987) - 1985
- [j42]David S. Johnson, M. R. Garey:
A 71/60 theorem for bin packing. J. Complex. 1(1): 65-106 (1985) - [j41]Fan R. K. Chung, Michael R. Garey, Robert Endre Tarjan:
Strongly connected orientations of mixed multigraphs. Networks 15(4): 477-484 (1985) - [j40]M. R. Garey, David S. Johnson:
Composing Functions to Minimize Image Size. SIAM J. Comput. 14(2): 500-503 (1985) - [j39]Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh:
Scheduling File Transfers. SIAM J. Comput. 14(3): 744-780 (1985) - 1984
- [j38]Michael R. Garey, Ron Y. Pinter:
Optimum scan-width selection under containment constraints. AT&T Bell Lab. Tech. J. 63(6): 1191-1212 (1984) - [j37]F. R. K. Chung, M. R. Garey:
Diameter bounds for altered graphs. J. Graph Theory 8(4): 511-534 (1984) - [j36]Ashok K. Agrawala, Edward G. Coffman Jr., M. R. Garey, Satish K. Tripathi:
A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniform Processors. IEEE Trans. Computers 33(4): 351-356 (1984) - 1983
- [j35]Edward G. Coffman Jr., M. R. Garey, David S. Johnson:
Dynamic Bin Packing. SIAM J. Comput. 12(2): 227-258 (1983) - [c8]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
- [j34]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
- [j33]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
- [j32]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) - [j31]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)
1970 – 1979
- 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
- [j30]M. R. Garey, Ronald L. Graham, David S. Johnson:
Performance Guarantees for Scheduling Algorithms. Oper. Res. 26(1): 3-21 (1978) - [j29]M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan:
Triangulating a Simple Polygon. Inf. Process. Lett. 7(4): 175-179 (1978) - [j28]M. R. Garey, Robert Endre Tarjan:
A Linear-Time Algorithm for Finding All Feedback Vertices. Inf. Process. Lett. 7(6): 274-276 (1978) - [j27]M. R. Garey, David S. Johnson:
"Strong" NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25(3): 499-508 (1978) - [j26]William M. Boyce, M. R. Garey, David S. Johnson:
A note on bisecting minimum spanning trees. Networks 8(3): 187-192 (1978) - [j25]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) - [j24]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
- [j23]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) - [j22]Alfred V. Aho, Michael R. Garey, Frank K. Hwang:
Rectilinear steiner trees: Efficient special-case algorithms. Networks 7(1): 37-58 (1977) - [j21]M. R. Garey, David S. Johnson:
The Rectilinear Steiner Tree Problem is NP Complete. SIAM Journal of Applied Mathematics 32: 826-834 (1977) - [j20]M. R. Garey, David S. Johnson:
Two-Processor Scheduling with Start-Times and Deadlines. SIAM J. Comput. 6(3): 416-426 (1977) - [j19]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
- [j18]Peter Gordon Anderson, M. R. Garey, Lee E. Heindel:
Computational aspects of deciding if all roots of a polynomial lie within the unit circle. Computing 16(4): 293-304 (1976) - [j17]M. Edelberg, M. R. Garey, Ronald L. Graham:
On the distance matrix of a tree. Discret. Math. 14(1): 23-39 (1976) - [j16]M. R. Garey, David S. Johnson:
The Complexity of Near-Optimal Graph Coloring. J. ACM 23(1): 43-49 (1976) - [j15]M. R. Garey, David S. Johnson:
Scheduling Tasks with Nonuniform Deadlines on Two Processors. J. ACM 23(3): 461-467 (1976) - [j14]M. R. Garey, Ronald L. Graham, David S. Johnson, Andrew Chi-Chih Yao:
Resource Constrained Scheduling as Generalized Bin Packing. J. Comb. Theory A 21(3): 257-298 (1976) - [j13]Michael R. Garey, David S. Johnson, Ravi Sethi:
The Complexity of Flowshop and Jobshop Scheduling. Math. Oper. Res. 1(2): 117-129 (1976) - [j12]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) - [j11]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
- [j10]Yehoshua Perl, M. R. Garey, Shimon Even:
Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters. J. ACM 22(2): 202-214 (1975) - [j9]M. R. Garey, Ronald L. Graham:
Bounds for Multiprocessor Scheduling with Resource Constraints. SIAM J. Comput. 4(2): 187-200 (1975) - [j8]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
- [j7]M. R. Garey, Ronald L. Graham:
Performance Bounds on the Splitting Algorithm for Binary Testing. Acta Informatica 3: 347-355 (1974) - [j6]M. R. Garey:
Optimal Binary Search Trees with Restricted Maximal Depth. SIAM J. Comput. 3(2): 101-110 (1974) - [j5]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 - 1973
- [j4]M. R. Garey:
Optimal task sequencing with precedence constraints. Discret. Math. 4(1): 37-56 (1973) - [c2]M. R. Garey, Ronald L. Graham:
Bounds on Scheduling with Limited Resources. SOSP 1973: 104-111 - 1972
- [j3]Alfred V. Aho, M. R. Garey, Jeffrey D. Ullman:
The Transitive Reduction of a Directed Graph. SIAM J. Comput. 1(2): 131-137 (1972) - [j2]Michael Randolph Garey:
Resident-Bubble Cellular Logic Using Magnetic Domains. IEEE Trans. Computers 21(4): 392-396 (1972) - [j1]Michael Randolph Garey:
Simple Binary Identification Problems. IEEE Trans. Computers 21(6): 588-590 (1972) - [c1]M. R. Garey, Ronald L. Graham, Jeffrey D. Ullman:
Worst-Case Analysis of Memory Allocation Algorithms. STOC 1972: 143-150
Coauthor Index
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 2024-10-30 20:32 CET 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: