{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T18:31:25Z","timestamp":1725388285867},"reference-count":32,"publisher":"IEEE Comput. Soc. Press","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sct.1994.315789","type":"proceedings-article","created":{"date-parts":[[2002,12,17]],"date-time":"2002-12-17T09:32:51Z","timestamp":1040117571000},"page":"356-366","source":"Crossref","is-referenced-by-count":4,"title":["Generalized CNF satisfiability problems and non-efficient approximability"],"prefix":"10.1109","author":[{"given":"H.B.","family":"Hunt","sequence":"first","affiliation":[]},{"given":"M.V.","family":"Marathe","sequence":"additional","affiliation":[]},{"given":"R.E.","family":"Stearns","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1993.336517"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57182-5_66"},{"journal-title":"Computers and Intractability A Guide to the Theory of NP-Completeness","year":"1979","author":"garey","key":"ref10"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/0216011"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/0216059"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/0219003"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90246-E"},{"key":"ref15","first-page":"377","article-title":"On the Approximability of the Maximum Common Subgraph Problem","author":"kann","year":"1992","journal-title":"Proc 9th Annual Symposium on Theoretical Aspects of Computer Science"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56939-1_61"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0039598"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"journal-title":"On the complexity of the satisfiability problem and the structure of NP","year":"1986","author":"stearns","key":"ref28"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.7"},{"key":"ref27","first-page":"136","article-title":"Satisfiability is quasilmeat complete for NQL","author":"schnorr","year":"1976","journal-title":"J ACM"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090776"},{"journal-title":"Interactive proofs and approximation","year":"0","author":"bellare","key":"ref5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167190"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267823"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1994.315796"},{"key":"ref1","first-page":"2","article-title":"Probabilistic Checking of Proofs","author":"arora","year":"1992","journal-title":"Annu Symp Foundations of Computer Science (FOCS)"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167172"},{"journal-title":"Dynamic programming on graphs with bounded treewidth","year":"1987","author":"bodlaender","key":"ref7a"},{"year":"0","key":"ref7b"},{"key":"ref22","article-title":"Quasilinear Time Complexity Theory","author":"naik","year":"1994","journal-title":"Proc of the Symposium on Theoretical Aspects of Computer Science (STACS)"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56939-1_63"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100275"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"journal-title":"Two Papers on Graph Embedding problems","year":"1980","author":"saxe","key":"ref25"}],"event":{"name":"IEEE 9th Annual Conference on Structure in Complexity Theory","acronym":"SCT-94","location":"Amsterdam, Netherlands"},"container-title":["Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx2\/967\/7616\/00315789.pdf?arnumber=315789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,9]],"date-time":"2017-03-09T05:15:43Z","timestamp":1489036543000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/315789\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":32,"URL":"https:\/\/doi.org\/10.1109\/sct.1994.315789","relation":{},"subject":[]}}