{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T10:38:34Z","timestamp":1772620714136,"version":"3.50.1"},"reference-count":43,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1982,6,1]],"date-time":"1982-06-01T00:00:00Z","timestamp":391737600000},"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,6]]},"DOI":"10.1016\/0196-6774(82)90018-9","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T08:44:36Z","timestamp":1108025076000},"page":"182-195","source":"Crossref","is-referenced-by-count":87,"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)90018-9_BIB1","article-title":"Calculating bounds on certain measures of network reliability","author":"Ball","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB2","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems","author":"Berlekamp","year":"1978","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0196-6774(82)90018-9_BIB3","series-title":"Optimal tile salvage","author":"Berman","year":"1982"},{"key":"10.1016\/0196-6774(82)90018-9_BIB4","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/0211015","article-title":"Dominating sets in chordal graphs","volume":"11","author":"Booth","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90018-9_BIB5","unstructured":"S. Burr, private communication, 1982."},{"key":"10.1016\/0196-6774(82)90018-9_BIB6","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1137\/0602042","article-title":"Covering regions by rectangles","volume":"2","author":"Chaiken","year":"1981","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"10.1016\/0196-6774(82)90018-9_BIB7","article-title":"Computational Geometry and Convexity","author":"Chazelle","year":"1980"},{"key":"10.1016\/0196-6774(82)90018-9_BIB8","series-title":"Proceedings 13th Ann. ACM Symp. on Theory of Computing","first-page":"70","article-title":"Convex decomposition of polyhedra","author":"Chazelle","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB9","series-title":"Proceedings 11th Ann. ACM Symp. on Theory of Computing","first-page":"38","article-title":"Decomposing a polygon into its convex parts","author":"Chazelle","year":"1979"},{"key":"10.1016\/0196-6774(82)90018-9_BIB10","doi-asserted-by":"crossref","DOI":"10.1145\/800135.804396","article-title":"Decomposing a polygon into its convex parts","author":"Chazelle","year":"1979"},{"key":"10.1016\/0196-6774(82)90018-9_BIB11","article-title":"Colouring block designs is NP-complete","author":"Colbourn","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB12","doi-asserted-by":"crossref","unstructured":"C. J. Colbourn, M. J. Colbourn, K. T. Phelps, and V. R\u00f6dl, Colouring Steiner quadruple systems, Discrete Applied Math., to appear.","DOI":"10.1016\/0166-218X(82)90068-3"},{"key":"10.1016\/0196-6774(82)90018-9_BIB13","article-title":"Estimation of sparse Jacobean matrices and graph coloring problems","author":"Coleman","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB14","article-title":"The NP-completeness of the crossing number problem with implications for VLSI layout","author":"Dewdney","year":"1982"},{"key":"10.1016\/0196-6774(82)90018-9_BIB15","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","article-title":"Optimal packing and covering in the plane are NP-complete","volume":"12","author":"Fowler","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(82)90018-9_BIB16","unstructured":"A. M. Frieze, \u201cOn equitably partitioning a connected graph into connected subgraphs,\u201d Technical Report, Department of Computer Science, Queen Mary College, London."},{"key":"10.1016\/0196-6774(82)90018-9_BIB17","series-title":"Partitioning a directed graph into two acyclic subgraphs is NP-complete","author":"G\u00e1cs","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB18","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/0210054","article-title":"The NP-completeness of some edge-partition problems","volume":"10","author":"Holyer","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90018-9_BIB19","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","article-title":"The NP-completeness of edge-coloring","volume":"10","author":"Holyer","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(82)90018-9_BIB20","article-title":"On the complexity of a parity problem related to coding theory","author":"Ja'Ja'","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB21","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1287\/mnsc.18.7.401","article-title":"A procedure for optimizing the K best solutions to discrete optimization problems and its application to the shortest path problem","volume":"18","author":"Lawler","year":"1972","journal-title":"Management Sci."},{"key":"10.1016\/0196-6774(82)90018-9_BIB22","series-title":"The power of non-rectilinear holes","author":"Lingas","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB23","series-title":"Heuristics for minimum edge length rectangular partition","author":"Lingas","year":"1982"},{"key":"10.1016\/0196-6774(82)90018-9_BIB24","series-title":"Minimum edge length decomposition of rectilinear polygons","author":"Lingas","year":"1982"},{"key":"10.1016\/0196-6774(82)90018-9_BIB25","doi-asserted-by":"crossref","DOI":"10.3233\/FI-1978-2114","article-title":"On two dimensional data organization II","volume":"2","author":"Lodi","year":"1979","journal-title":"Fundamenta Informaticae"},{"key":"10.1016\/0196-6774(82)90018-9_BIB26","unstructured":"M. Luby, private communication, 1981."},{"key":"10.1016\/0196-6774(82)90018-9_BIB27","series-title":"talk presented at the 13th Southeastern Conference on Combinatorics, Graph Theory, and Computing","article-title":"On a moderately exponential isomorphism test","author":"Luks","year":"1982"},{"key":"10.1016\/0196-6774(82)90018-9_BIB28","first-page":"57","article-title":"The computational complexity of the m-center problems on the plane","volume":"E64","author":"Masuyama","year":"1981","journal-title":"Trans. IECE of Japan"},{"key":"10.1016\/0196-6774(82)90018-9_BIB29","doi-asserted-by":"crossref","DOI":"10.21236\/ADA110846","article-title":"Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem","author":"McCormick","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB30","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1109\/TIT.1981.1056419","article-title":"On the complexity of some coding problems","author":"Ntafos","year":"1981","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/0196-6774(82)90018-9_BIB31","article-title":"Minimum convex covers for polygons: Some counterexamples","author":"O'Rourke","year":"1982"},{"key":"10.1016\/0196-6774(82)90018-9_BIB32","article-title":"Some NP-hard polygon decomposition problems","author":"O'Rourke","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB33","doi-asserted-by":"crossref","unstructured":"K. T. Phelps, private communication, 1982.","DOI":"10.1055\/s-1982-29761"},{"key":"10.1016\/0196-6774(82)90018-9_BIB34","series-title":"On the algorithmic complexity of coloring simple hypergraphs and. Steiner triple systems","author":"Phelps","year":"1982"},{"key":"10.1016\/0196-6774(82)90018-9_BIB35","unstructured":"R. Y. Pinter, private communication, 1982."},{"key":"10.1016\/0196-6774(82)90018-9_BIB36","doi-asserted-by":"crossref","first-page":"1060","DOI":"10.1137\/0716078","article-title":"On the estimation of sparse Hessian matrices","volume":"16","author":"Powell","year":"1979","journal-title":"SIAM J. Numer. Anal."},{"key":"10.1016\/0196-6774(82)90018-9_BIB37","article-title":"The complexity of counting cuts and of computing the probability that a graph is connected","author":"Provan","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB38","first-page":"42","article-title":"A note on sum-distinct sets and a problem of Erd\u00f6s","volume":"2","author":"Rubin","year":"1981","journal-title":"Abstracts of the AMS"},{"key":"10.1016\/0196-6774(82)90018-9_BIB39","unstructured":"T. J. Schaefer, private communication, 1974."},{"key":"10.1016\/0196-6774(82)90018-9_BIB40","series-title":"Proceedings 11th Ann. ACM Symp. on Theory of Computing","first-page":"118","article-title":"On the cryptocomplexity of knapsack systems","author":"Shamir","year":"1979"},{"key":"10.1016\/0196-6774(82)90018-9_BIB41","article-title":"Topics in computational geometry","author":"Supowit","year":"1981"},{"key":"10.1016\/0196-6774(82)90018-9_BIB42","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1145\/322217.322220","article-title":"An algorithm to enumerate all cutsets of a graph in linear time per cutset","volume":"27","author":"Tsukiyama","year":"1980","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(82)90018-9_BIB43","article-title":"Another NP-complete partition problem and the complexity of computing short vectors in a lattice","author":"van Emde Boas","year":"1981"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677482900189?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677482900189?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T00:01:32Z","timestamp":1625443292000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677482900189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1982,6]]}},"alternative-id":["0196677482900189"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(82)90018-9","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1982,6]]}}}