{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:47:57Z","timestamp":1763466477433},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540779179"},{"type":"electronic","value":"9783540779186"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77918-6_14","type":"book-chapter","created":{"date-parts":[[2008,2,8]],"date-time":"2008-02-08T08:41:19Z","timestamp":1202460079000},"page":"170-183","source":"Crossref","is-referenced-by-count":2,"title":["The Minimum Substring Cover Problem"],"prefix":"10.1007","author":[{"given":"Danny","family":"Hermelin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"Johnson, D.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences\u00a09, 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1974","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integeral and fractional solutions. Discrete Mathematics\u00a013, 383\u2013390 (1974)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"14_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04(3), 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D. Hochbaum","year":"1982","unstructured":"Hochbaum, D.: Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing\u00a011(3), 555\u2013556 (1982)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms\u00a02, 198\u2013203 (1981)","journal-title":"Journal of Algorithms"},{"key":"14_CR6","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"14_CR7","first-page":"49","volume":"11","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Downey, R., Fellows, M., Hallett, M., Wareham, H.: Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences\u00a011(1), 49\u201357 (1995)","journal-title":"Computer Applications in the Biosciences"},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1016\/0959-440X(91)90093-9","volume":"1","author":"R. Dorit","year":"1991","unstructured":"Dorit, R., Gilbert, W.: The limited universe of exons. Current Opinions in Structural Biology\u00a01, 973\u2013977 (1991)","journal-title":"Current Opinions in Structural Biology"},{"issue":"4","key":"14_CR9","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1002\/bies.950130408","volume":"13","author":"L. Patthy","year":"1991","unstructured":"Patthy, L.: Exons - original building blocks of proteins? BioEssays\u00a013(4), 187\u2013192 (1991)","journal-title":"BioEssays"},{"key":"14_CR10","volume-title":"Handbook of Formal Languages","author":"C. Choffrut","year":"1997","unstructured":"Choffrut, C., Karhum\u00e4ki, J.: Combinatorics of Words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Springer, Heidelberg (1997)"},{"issue":"5","key":"14_CR11","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1051\/ita\/1990240504591","volume":"24","author":"J. N\u00e9raud","year":"1990","unstructured":"N\u00e9raud, J.: Elementariness of a finite set of words is co-NP-complete. Theoretical Informatics and Applications\u00a024(5), 459\u2013470 (1990)","journal-title":"Theoretical Informatics and Applications"},{"key":"14_CR12","volume-title":"The Mathematical Theory of L Systems","author":"G. Rozenberg","year":"1980","unstructured":"Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems. Academic Press, London (1980)"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(78)90047-6","volume":"7","author":"A. Ehrenfeucht","year":"1978","unstructured":"Ehrenfeucht, A., Rozenberg, G.: Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoretical Computer Science\u00a07, 169\u2013183 (1978)","journal-title":"Theoretical Computer Science"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/11590156_13","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"R. Hassin","year":"2005","unstructured":"Hassin, R., Segev, D.: The set cover with pairs problem. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 164\u2013176. Springer, Heidelberg (2005)"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Huang, Y.T., Chao, K.M., Chen, T.: An approximation algorithm for haplotype inference by maximum parsimony. In: Proceedings of the 20\u2019th ACM Symposium on Applied Computing (SAC), pp. 146\u2013150 (2005)","DOI":"10.1145\/1066677.1066714"},{"key":"14_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/11758525_102","volume-title":"Computational Science \u2013 ICCS 2006","author":"M. Hajiaghayi","year":"2006","unstructured":"Hajiaghayi, M., Jain, K., Lau, L., Mandoiu, I.: Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J.J. (eds.) ICCS 2006. LNCS, vol.\u00a03991, pp. 758\u2013766. Springer, Heidelberg (2006)"},{"issue":"2","key":"14_CR17","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s004530010009","volume":"27","author":"R. Bar-Yehuda","year":"2000","unstructured":"Bar-Yehuda, R.: One for the price of two: A unified approach for approximating covering problems. Algorithmica\u00a027(2), 131\u2013144 (2000)","journal-title":"Algorithmica"},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and Systems Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th ACM Symposium on the Theory Of Computing (STOC), pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"issue":"5","key":"14_CR20","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM Journal on Computing\u00a034(5), 1129\u20131146 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-62592-5_80","volume-title":"Algorithms and Complexity","author":"P. Alimonti","year":"1997","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol.\u00a01203, pp. 288\u2013298. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77918-6_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:56:14Z","timestamp":1619520974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77918-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540779179","9783540779186"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77918-6_14","relation":{},"subject":[]}}