{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T05:27:01Z","timestamp":1773898021361,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,17]],"date-time":"2015-04-17T00:00:00Z","timestamp":1429228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00453-015-9996-7","type":"journal-article","created":{"date-parts":[[2015,4,16]],"date-time":"2015-04-16T14:34:44Z","timestamp":1429194884000},"page":"1267-1292","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Configurations and Minority in the String Consensus Problem"],"prefix":"10.1007","volume":"74","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Paryenty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,17]]},"reference":[{"key":"9996_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Landau, G.M., Na, J.C., Park, H., Park, K., Sim, J.S.: Consensus optimizing both distance sum and radius. In: Kalgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) Proceedings of 16th Symposium on String Processing and Information Retrieval (SPIRE), LNCS, vol. 5721. Springer, pp. 234\u2013242 (2009)","DOI":"10.1007\/978-3-642-03784-9_23"},{"key":"9996_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Paryenty, H., Roditty, L.: Approximations and partial solutions for the consensus sequence problem. In: Proceedings of 18th Symposium on String Processing and Information Retrieval (SPIRE) (2011, to appear)","DOI":"10.1007\/978-3-642-24583-1_17"},{"key":"9996_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P., Patrascu, M.: On the optimality of the dimensionality reduction method. In: Proceedings of 47th IEEE Symposium on the Foundation of Computer Science (FOCS), pp. 449\u2013458 (2006)","DOI":"10.1109\/FOCS.2006.56"},{"key":"9996_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Dor, A., Lancia, G., Perone, J., Ravi, R.: Banishing bias from consensus sequences. In: Proceedings of 8th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 247\u2013261 (1997)","DOI":"10.1007\/3-540-63220-4_63"},{"key":"9996_CR5","doi-asserted-by":"crossref","unstructured":"Boucher, C., Brown, D., Durocher, S.: On the structure of small motif recognition instances. In: Proceedings of 15th Symposium on String Processing and Information Retrieval (SPIRE), pp. 269\u2013281 (2008)","DOI":"10.1007\/978-3-540-89097-3_26"},{"key":"9996_CR6","doi-asserted-by":"crossref","unstructured":"Boucher, C., Wilkie, K.: Why large closest string instances are easy to solve in practice. In: Proceedings of 17th Symposium on String Processing and Information Retrieval (SPIRE), pp. 106\u2013117 (2010)","DOI":"10.1007\/978-3-642-16321-0_10"},{"key":"9996_CR7","doi-asserted-by":"crossref","unstructured":"Chimani, M., Woste, M., Bocker, S.: A closer look at the closest string and closest substring problem. In: Proceedings of 13th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 13\u201324 (2011)","DOI":"10.1137\/1.9781611972917.2"},{"key":"9996_CR8","unstructured":"Evans, P.A., Smith, A., Wareham, H.T.: The Parameterized Complexity of p-Center Approximate Substring Problems. Technical Report TR01-149, Faculty of Computer Science, University of New Brunswick, Canada (2001)"},{"issue":"2","key":"9996_CR9","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02679443","volume":"30","author":"M Frances","year":"1997","unstructured":"Frances, M., Litman, A.: On covering problems of codes. Theory Comput. Syst. 30(2), 113\u2013119 (1997)","journal-title":"Theory Comput. Syst."},{"key":"9996_CR10","doi-asserted-by":"crossref","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Exact solutions for closest string and related problems. In: Eades, P., Takaoka, T. (eds.) Proceedings of 12th Annual Symposium on Algorithms and Computation (ISAAC), LNCS, vol. 2223. Springer, pp. 441\u2013453 (2001)","DOI":"10.1007\/3-540-45678-3_38"},{"issue":"1","key":"9996_CR11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s00453-003-1028-3","volume":"37","author":"J Gramm","year":"2003","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Fixed-parameter algorithms for closest string and related problems. Algorithmica 37(1), 25\u201342 (2003)","journal-title":"Algorithmica"},{"key":"9996_CR12","doi-asserted-by":"crossref","unstructured":"Hufsky, F., Kuchenbecker, L., Jahn, K., Stoye, J., Bocker, S.: Swiftly computing center strings. In: Proceedings of 10th Workshop on Algorithms in Bioinformatics (WABI), pp. 325\u2013336 (2010)","DOI":"10.1007\/978-3-642-15294-8_27"},{"issue":"1","key":"9996_CR13","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"K Lanctot","year":"2003","unstructured":"Lanctot, K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Inf. Comput. 185(1), 41\u201355 (2003)","journal-title":"Inf. Comput."},{"key":"9996_CR14","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"9996_CR15","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the closest string and substring problems. J. ACM 49(2), 157\u2013171 (2002)","journal-title":"J. ACM"},{"issue":"4","key":"9996_CR16","doi-asserted-by":"crossref","first-page":"1432","DOI":"10.1137\/080739069","volume":"39","author":"B Ma","year":"2009","unstructured":"Ma, B., Sun, X.: More efficient algorithms for closest string and substring problems. SIAM J. Comput. 39(4), 1432\u20131443 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9996_CR17","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1287\/ijoc.1040.0090","volume":"16","author":"CN Meneses","year":"2004","unstructured":"Meneses, C.N., Lu, Z., Oliveira, C.A.S., Pardalos, P.M.: Optimal solutions for the closest-string problem via integer programming. INFORMS J. Comput. 16(4), 419\u2013429 (2004)","journal-title":"INFORMS J. Comput."},{"key":"9996_CR18","doi-asserted-by":"crossref","unstructured":"Stojanovic, N., Berman, P., Gumucio, D., Hardison, R., Miller, W.: A linear-time algorithm for the 1-mismatch problem. In: Proceedings of 5th International Workshop on Algorithms and Data Structures (WADS), pp. 126\u2013135 (1997)","DOI":"10.1007\/3-540-63307-3_53"},{"key":"9996_CR19","doi-asserted-by":"crossref","unstructured":"Sze, S., Lu, S., Chen, J.: Integrating sample-driven and pattern-driven approaches in motif finding. In: Proceedings of 4th Workshop on Algorithms in Bioinformatics (WABI), pp. 438\u2013449 (2004)","DOI":"10.1007\/978-3-540-30219-3_37"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9996-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9996-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9996-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T15:41:03Z","timestamp":1566574863000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9996-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,17]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9996"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9996-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,17]]}}}