{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T19:54:11Z","timestamp":1648583651181},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p> Given a string s on an alphabet \u03a3, a word-length k and a budget D, we want to determine the smallest number of distinct k-mers that can be left in s, if we are allowed to replace up to D letters of s. This problem has several parameters, and we discuss its complexity under all sorts of restrictions on the parameters values. We prove that some versions of the problem are polynomial, while others are NP-hard. We also introduce some Integer Programming formulations to model the NP-hard cases. <\/jats:p>","DOI":"10.1142\/s0129054108005504","type":"journal-article","created":{"date-parts":[[2008,2,20]],"date-time":"2008-02-20T04:46:31Z","timestamp":1203482791000},"page":"5-17","source":"Crossref","is-referenced-by-count":0,"title":["FLIPPING LETTERS TO MINIMIZE THE SUPPORT OF A STRING"],"prefix":"10.1142","volume":"19","author":[{"given":"GIUSEPPE","family":"LANCIA","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Udine, Via delle Scienze 206, Udine, 33100, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FRANCA","family":"RINALDI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Udine, Via delle Scienze 206, Udine, 33100, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ROMEO","family":"RIZZI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, University of Udine, Via delle Scienze 206, Udine, 33100, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"758","volume":"49","author":"de Bruijn N. D.","journal-title":"Koninklijke Netherlands: Academe Van Wetenschappen"},{"key":"rf2","volume":"11","author":"Flaxman A.","journal-title":"The Electronic J. of Combinatorics"},{"key":"rf3","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf4","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"1996"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970166"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:29:10Z","timestamp":1565177350000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":5,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1142\/S0129054108005504"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005504","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]}}}