{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:20Z","timestamp":1725663260357},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540083535"},{"type":"electronic","value":"9783540372851"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08353-7_123","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:23:36Z","timestamp":1330187016000},"page":"1-16","source":"Crossref","is-referenced-by-count":1,"title":["On the structure and properties of NP-complete problems and their associated optimization problems"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Ausiello","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"unstructured":"A.AIELLO, E.BURATTINI, A.MASSAROTTI, F.VENTRIGLIA: Toward a general principle of evaluation for approximate algorithms. In S\u00e9minaires IRIA, Parigi, Francia, 1976.","key":"1_CR1"},{"unstructured":"G.AUSIELLO, A.D'ATRI, M.PROTASI: A characterization of reductions among combinatorial problems. R. 76\u201323, Istituto di Automatica, Universit\u00e0 di Roma, 1976.","key":"1_CR2"},{"doi-asserted-by":"crossref","unstructured":"G.AUSIELLO, A.D'ATRI, M.PROTASI: On the structure of combinatorial problems and structure preserving reductions. Proc. 4 th International Colloquium on Automata, Languages and Programming, Turku, Finland, 1977a.","key":"1_CR3","DOI":"10.1007\/3-540-08342-1_4"},{"doi-asserted-by":"crossref","unstructured":"G.AUSIELLO, A.D'ATRI, M.GAUDIANO, M.PROTASI: Classes of structurally isomorphic NP optimization problems. These proceedings 1977b.","key":"1_CR4","DOI":"10.1007\/3-540-08353-7_139"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. BAKER, J. GILL, R. SOLOVAY: Relativizations of the P = ? NP question. SIAM J. on Computing, 4, 4, 1975.","journal-title":"SIAM J. on Computing"},{"doi-asserted-by":"crossref","unstructured":"L.BERMAN, J.HARTMANIS: On polynomial time isomorphisms of complete sets. 3 rd GI Conference on Theoretical Computer Science, Darmstadt, Germany, 1977.","key":"1_CR6","DOI":"10.1007\/3-540-08138-0_1"},{"doi-asserted-by":"crossref","unstructured":"S.COOK: The complexity of theorem proving procedures. Proc. 3 rd Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, USA, 1971.","key":"1_CR7","DOI":"10.1145\/800157.805047"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"M. R. Garey","year":"1976","unstructured":"M.R. GAREY, D.S. JOHNSON: The complexity of near optimal graph coloring. J. ACM, 23, 1, 1976a.","journal-title":"J. ACM"},{"unstructured":"M.R.GAREY, D.S.JOHNSON: Approximation algorithms for combinatorial problems: an annotated bibliography. Proc. Symposium on Algorithms and Complexity: New directions and recent results, Pittsburg, Pa, USA, 1976b.","key":"1_CR9"},{"doi-asserted-by":"crossref","unstructured":"J.HARTMANIS, L.BERMAN: On isomorphism and density of NP and other complete sets. Proc. 8 th Annual ACM Symposium on Theory of Computing, Hershey, Pa., USA, 1976.","key":"1_CR10","DOI":"10.1145\/800113.803628"},{"doi-asserted-by":"crossref","unstructured":"J.HARTMANIS, J.E.HOPCROFT: Independence results in computer science. TR, Department of Computer Science, Cornell University, Ithaca, N.Y., USA, 1976.","key":"1_CR11","DOI":"10.1145\/1008335.1008336"},{"doi-asserted-by":"crossref","unstructured":"J.HARTMANIS, J.SIMON: On the structure of feasible computations. In Advances in Computers, Vol. 14, Academic Press, N.Y., 1976.","key":"1_CR12","DOI":"10.1016\/S0065-2458(08)60449-0"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321906.321909","volume":"22","author":"O. H. Ibarra","year":"1975","unstructured":"O.H. IBARRA, C.E. KIM: Fast approximation algorithms for the Knapsack and sum of subsets problems. J. ACM, 22, 4, 1975.","journal-title":"J. ACM"},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D.S. JOHNSON: Approximation algorithms for combinatorial problems. J. Computers and Systems Science, 9, 3, 1974.","journal-title":"J. Computers and Systems Science"},{"doi-asserted-by":"crossref","unstructured":"R.KARP: Reducibilities among combinatorial problems. In Complexity of Computer Computations, Plenum Press, 1972.","key":"1_CR15","DOI":"10.1007\/978-1-4684-2001-2_9"},{"doi-asserted-by":"crossref","unstructured":"C.H.PAPADIMITRIOU, K.STEIGLITZ: Some complexity results for the traveling salesman problem. Proc. 8 th Annual ACM Symposium on Theory of Computing, Hershey, Pa., USA, 1976.","key":"1_CR16","DOI":"10.1145\/800113.803625"},{"doi-asserted-by":"crossref","unstructured":"A.PAZ, S.MORAN: Non-deterministic polynomial optimization problems and their approximation. Proc. 4 th International Colloquium on Automata, Languages and Programming, Turku, Finland, 1977.","key":"1_CR17","DOI":"10.1007\/3-540-08342-1_29"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321864.321873","volume":"22","author":"S. Sahni","year":"1975","unstructured":"S. SAHNI: Approximate algorithms for the 0\u20131 Knapsack problem. J. ACM, 22 1, 1975.","journal-title":"J. ACM"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. SAHNI: Algorithms for scheduling independent tasks. J. ACM, 23, 1, 1976.","journal-title":"J. ACM"},{"key":"1_CR20","first-page":"3","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. SAHNI, T. GONZALES: P-complete approximation problems. J. ACM, 23, 3, 1976.","journal-title":"J. ACM"},{"unstructured":"J.SIMON: On some central problems in computational complexity. TR 75\u2013224, Department of Computer Science, Cornell University, Ithaca, N.Y., USA, 1975.","key":"1_CR21"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1977"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08353-7_123.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:59:17Z","timestamp":1605643157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08353-7_123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083535","9783540372851"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-08353-7_123","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}