{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:43:41Z","timestamp":1759063421083},"reference-count":45,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1982,9,1]],"date-time":"1982-09-01T00:00:00Z","timestamp":399686400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[1982,9]]},"DOI":"10.1016\/0196-6774(82)90026-8","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T08:44:36Z","timestamp":1108025076000},"page":"288-300","source":"Crossref","is-referenced-by-count":29,"title":["The NP-completeness column: An ongoing guide"],"prefix":"10.1016","volume":"3","author":[{"given":"David S","family":"Johnson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(82)90026-8_BIB1","series-title":"Proceedings 9th Ann. ACM Symp. on Theory of Computing","first-page":"151","article-title":"Reducibility, randomness, and intractability","author":"Adleman","year":"1977"},{"key":"10.1016\/0196-6774(82)90026-8_BIB2","author":"Aho","year":"1972"},{"key":"10.1016\/0196-6774(82)90026-8_BIB3","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di, in preparation, (1982)."},{"key":"10.1016\/0196-6774(82)90026-8_BIB4","first-page":"73","article-title":"NP-completeness of the Hamiltonian cycle problem for bipartite graphs","volume":"3","author":"Akiyama","year":"1980","journal-title":"Journal of Information Processing"},{"key":"10.1016\/0196-6774(82)90026-8_BIB5","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/0602041","article-title":"The bandwidth of caterpillars with hairs of length 1 and 2","volume":"2","author":"Assman","year":"1981","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10.1016\/0196-6774(82)90026-8_BIB6","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","article-title":"Relativizations of the P = ? NP question","volume":"4","author":"Baker","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90026-8_BIB7","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","article-title":"Relative to a random oracle A, PA \u2260 NPA \u2260 co\u2212NPA with p robability 1","volume":"10","author":"Bennett","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90026-8_BIB8","series-title":"Polynomial algorithms for the min cut problem on degree restricted trees","author":"Chung","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB9","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0196-6774(81)90029-8","article-title":"The minimum-length generator sequence problem is NP-hard","volume":"2","author":"Even","year":"1981","journal-title":"J. Algorithms"},{"key":"10.1016\/0196-6774(82)90026-8_BIB10","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","article-title":"Bin packing can be solved within 1 + \u03f5 in linear time","volume":"1","author":"Fernandez de la Vega","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/0196-6774(82)90026-8_BIB11","series-title":"Analysis of a compound bin packing algorithm","author":"Friesen","year":"1981"},{"key":"10.1016\/0196-6774(82)90026-8_BIB12","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0134037","article-title":"Complexity results for bandwidth minimization","volume":"34","author":"Garey","year":"1978","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/0196-6774(82)90026-8_BIB13","series-title":"Proceedings 4th Ann. ACM Symp. on Theory of Computing","first-page":"143","article-title":"Worst-case analysis of memory allocation algorithms","author":"Garey","year":"1972"},{"key":"10.1016\/0196-6774(82)90026-8_BIB14","series-title":"A 7160 algorithm for one-dimensional bin packing","author":"Garey","year":"1980"},{"key":"10.1016\/0196-6774(82)90026-8_BIB15","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","article-title":"A linear programming approach to the cutting-stock problem","volume":"9","author":"Gilmore","year":"1961","journal-title":"Operations Res."},{"key":"10.1016\/0196-6774(82)90026-8_BIB16","unstructured":"R. L. Graham and R. W. Robinson, private communication (1982)."},{"key":"10.1016\/0196-6774(82)90026-8_BIB17","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/0196-6774(82)90026-8_BIB18","series-title":"Isomorphic factorizations VIII: Bisectable trees","author":"Harary","year":"1981"},{"key":"10.1016\/0196-6774(82)90026-8_BIB19","article-title":"Eigenschaften von Petrinetzsprachen","author":"Jantzen","year":"1979"},{"key":"10.1016\/0196-6774(82)90026-8_BIB20","article-title":"Near-optimal bin packing algorithms","author":"Johnson","year":"1973"},{"key":"10.1016\/0196-6774(82)90026-8_BIB21","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","article-title":"Fast algorithms for bin packing","volume":"8","author":"Johnson","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(82)90026-8_BIB22","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","article-title":"Worstcase performance bounds for simple one-dimensional packing algorithms","volume":"3","author":"Johnson","year":"1974","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90026-8_BIB23","series-title":"Proceedings 23rd Ann. Symp. on Foundations of Computer Science","article-title":"An efficient approximation scheme for the one dimensional bin packing problem","author":"Karp","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB24","author":"Knuth","year":"1973"},{"key":"10.1016\/0196-6774(82)90026-8_BIB25","series-title":"Proceedings 14th Ann. ACM Symp. on Theory of Computing","first-page":"224","article-title":"On the random oracle hypothesis","author":"Kurtz","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB26","series-title":"Recontamination does not help","author":"LaPaugh","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB27","series-title":"On some variants of the bandwidth minimization problem","author":"Leung","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB28","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","article-title":"Planar formulae and their uses","volume":"11","author":"Lichtenstein","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90026-8_BIB29","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1137\/0210002","article-title":"Some NP-complete problems similar to graph isomorphism","volume":"10","author":"Lubiw","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90026-8_BIB30","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","article-title":"A note on the graph isomorphism counting problem","volume":"8","author":"Mathon","year":"1979","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(82)90026-8_BIB31","series-title":"Proceedings 22nd Ann. Symp. on Foundations of Computer Science","first-page":"376","article-title":"The complexity of searching a graph (preliminary version)","author":"Megiddo","year":"1981"},{"key":"10.1016\/0196-6774(82)90026-8_BIB32","series-title":"Proceedings 23rd Ann. Symp. on Foundations of Computer Science","article-title":"On the complexity of unique solutions","author":"Papadimitriou","year":"1981"},{"key":"10.1016\/0196-6774(82)90026-8_BIB33","series-title":"On two geometric problems related to the travelling salesman problem","author":"Papadimitriou","year":"1981"},{"key":"10.1016\/0196-6774(82)90026-8_BIB34","series-title":"Proceedings 14th Ann. ACM Symp. on Theory of Computing","first-page":"255","article-title":"The complexity of facets (and some facets of complexity)","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB35","series-title":"Theory and Application of Graphs","first-page":"426","article-title":"Pursuit-evasion in a graph","author":"Parsons","year":"1976"},{"key":"10.1016\/0196-6774(82)90026-8_BIB36","series-title":"Proceedings 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing","first-page":"549","article-title":"The search number of a connected graph","author":"Parsons","year":"1978"},{"key":"10.1016\/0196-6774(82)90026-8_BIB37","doi-asserted-by":"crossref","unstructured":"M. O. Rabin, private communication (1981).","DOI":"10.1515\/ijsl.1981.30.19"},{"key":"10.1016\/0196-6774(82)90026-8_BIB38","series-title":"The Hamiltonian path and cycle problems are P-time solvable for reducible flow graphs","author":"Ramanath","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB39","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1137\/0601042","article-title":"Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time","volume":"1","author":"Saxe","year":"1980","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10.1016\/0196-6774(82)90026-8_BIB40","article-title":"Untangling a traveling salesman tour in the plane","author":"van Leeuwen","year":"1980"},{"key":"10.1016\/0196-6774(82)90026-8_BIB41","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/872730.806460","article-title":"A graphics typesetting language","volume":"16","author":"Van Wyck","year":"1981","journal-title":"SIGPLAN Notices"},{"key":"10.1016\/0196-6774(82)90026-8_BIB42","article-title":"On the complexity of iterated shuffle","author":"Warmuth","year":"1981"},{"key":"10.1016\/0196-6774(82)90026-8_BIB43","article-title":"The complexity of the Hamiltonian circuit problem for maximal planar graphs","author":"Wigderson","year":"1982"},{"key":"10.1016\/0196-6774(82)90026-8_BIB44","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/322186.322187","article-title":"New algorithms for bin packing","volume":"27","author":"Yao","year":"1980","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(82)90026-8_BIB45","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0020-0190(79)90130-3","article-title":"Graph 2-isomorphism is NP-complete","volume":"9","author":"Yao","year":"1979","journal-title":"Inform. Process. Lett."}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677482900268?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677482900268?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T18:34:11Z","timestamp":1586111651000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677482900268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,9]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1982,9]]}},"alternative-id":["0196677482900268"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(82)90026-8","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1982,9]]}}}