{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T09:41:54Z","timestamp":1767865314599,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540613329","type":"print"},{"value":"9783540684619","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61332-3_163","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:34:23Z","timestamp":1330292063000},"page":"290-299","source":"Crossref","is-referenced-by-count":10,"title":["Approximating minimum keys and optimal substructure screens"],"prefix":"10.1007","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[]},{"given":"Feng","family":"Bao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0263-7855(84)80060-0","volume":"2","author":"S. Anderson","year":"1984","unstructured":"Anderson, S.: Graphical representation of molecules and substructure-search queries in MACCS. J. Molecular Graphics 2 (1984) 83\u201389","journal-title":"J. Molecular Graphics"},{"key":"31_CR2","first-page":"14","volume":"92","author":"S. Arora","year":"1992","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation algorithms. Proc. FOCS'92 (1992) 14\u201323","journal-title":"Proc. FOCS'"},{"key":"31_CR3","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/2422.322414","volume":"31","author":"C. Beeri","year":"1984","unstructured":"Beeri, C., Dowd, M., Fagin, R., Statman, R.: On the structure of armstrong relations for functional dependencies. J. ACM 31 (1984) 30\u201346","journal-title":"J. ACM"},{"key":"31_CR4","unstructured":"Crescenzi, P., Kann, V.: A compendium of NP optimization problems. Manuscript (1995)"},{"key":"31_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"31_CR6","unstructured":"Halld\u00f3rsson, M. M.: Approximating discrete collections via local improvement. Proc. SODA'95 (1995)"},{"key":"31_CR7","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common super sequences and longest common subsequences. Proc. ICALP'94, LNCS, Springer-Verlag (1994) 191\u2013202"},{"key":"31_CR8","first-page":"256","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"Johnson, D. S.: Approximation algorithms for combinatorial problems. JCSS 9 (1974) 256\u2013278","journal-title":"JCSS"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Kann, V.: Polynomially bounded minimization problems which are hard to approximate. Proc. ICALP'93, LNCS, Springer-Verlag (1993) 52\u201363","DOI":"10.1007\/3-540-56939-1_61"},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1006\/inco.1994.1100","volume":"115","author":"P. G. Kolaitis","year":"1994","unstructured":"Kolaitis, P. G., Thakur, M. N.: Logical definability of NP optimization problems. Information and Computation 115 (1994) 321\u2013353","journal-title":"Information and Computation"},{"key":"31_CR11","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Disc. Math. 13 (1975) 383\u2013390","journal-title":"Disc. Math."},{"key":"31_CR12","first-page":"270","volume":"17","author":"C. L. Lucchesi","year":"1978","unstructured":"Lucchesi, C. L., Osborn, S. L.: Candidate keys for relations. JCSS 17 (1978) 270\u2013279","journal-title":"JCSS"},{"key":"31_CR13","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41 (1994) 960\u2013981","journal-title":"J. ACM"},{"key":"31_CR14","first-page":"425","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H., Yannakakis, M.: Optimization, approximation, and complexity classes. JCSS 43 (1991) 425\u2013440","journal-title":"JCSS"},{"key":"31_CR15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1021\/ci60017a008","volume":"19","author":"M. Randic","year":"1979","unstructured":"Randic, M., Wilkins, C. L.: Graph-based fragment searches in polycyclic structures. J. Chemical Information and Computer Sciences 19 (1979) 23\u201331","journal-title":"J. Chemical Information and Computer Sciences"},{"key":"31_CR16","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1021\/ci00047a025","volume":"25","author":"R. E. Stobaugh","year":"1985","unstructured":"Stobaugh, R. E.: Chemical substructure searching. J. Chemical Information and Computer Sciences 25 (1985) 271\u2013275","journal-title":"J. Chemical Information and Computer Sciences"},{"key":"31_CR17","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1021\/c160016a007","volume":"5","author":"E. H. Sussenguth Jr.","year":"1965","unstructured":"Sussenguth, Jr. E. H.: A graph-theoretic algorithm for matching chemical structures. J. Chemical Documentation 5 (1965) 36\u201343","journal-title":"J. Chemical Documentation"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61332-3_163.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T10:32:56Z","timestamp":1640946776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61332-3_163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540613329","9783540684619"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-61332-3_163","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}