{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:40Z","timestamp":1759638880675,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540403111"},{"type":"electronic","value":"9783540448884"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"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":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44888-8_23","type":"book-chapter","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T16:34:12Z","timestamp":1173112452000},"page":"315-327","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Complexities of the Centre and Median String Problems"],"prefix":"10.1007","author":[{"given":"Fran\u00e7ois","family":"Nicolas","sequence":"first","affiliation":[]},{"given":"Eric","family":"Rivals","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,27]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0304-3975(97)00240-5","volume":"230","author":"C. Higuera de la","year":"2000","unstructured":"C. de la Higuera and F. Casacuberta. Topology of strings: Median string is NP-complete. Theoretical Computer Science, 230:39\u201348, 2000.","journal-title":"Theoretical Computer Science"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"X. Deng, G. Li, Z. Li, B. Ma, and L. Wang. A ptas for distinguishing (sub)string selection. In ICALP, pages 740\u2013751, 2002.","DOI":"10.1007\/3-540-45465-9_63"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Michael R. Fellows, Jens Gramm, and Rolf Niedermeier. On the parameterized intractability of CLOSEST SUBSTRING and related problems. In Symposium on Theoretical Aspects of Computer Science, pages 262\u2013273, 2002.","DOI":"10.1007\/3-540-45841-7_21"},{"key":"23_CR5","first-page":"441","volume":"2223","author":"J. Gramm","year":"2001","unstructured":"Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Exact solutions for CLOSEST STRING and related problems. In ISAAC, volume 2223 of LCNS, pages 441\u2013453, 2001.","journal-title":"ISAAC"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02460299","volume":"55","author":"D. Gusfield","year":"1993","unstructured":"Dan Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull. Math. Biol., 55:141\u2013154, 1993.","journal-title":"Bull. Math. Biol."},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Dan Gusfield. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"issue":"3","key":"23_CR8","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/BF01955679","volume":"16","author":"T. Jiang","year":"1996","unstructured":"Tao Jiang, Eugene L. Lawler, and Lusheng Wang. Approximation algorithms for tree alignment with a given phylogeny. Algorithmica, 16(3):302\u2013315, 1996.","journal-title":"Algorithmica"},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0167-8655(85)90061-3","volume":"3","author":"T. Kohonen","year":"1985","unstructured":"T. Kohonen. Median strings. Pattern Recognition Letters, 3:309\u2013313, 1985.","journal-title":"Pattern Recognition Letters"},{"key":"23_CR10","unstructured":"J. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang. Distinguishing string selection problems. In SODA: ACM-SIAM Symposium on Discrete Algorithms, 1999."},{"issue":"8","key":"23_CR11","first-page":"707","volume":"10","author":"V. I. Levenshtein","year":"1966","unstructured":"V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and Reverseals. Cybernetics and Control Theory, 10(8):707\u2013710, 1966.","journal-title":"Cybernetics and Control Theory"},{"issue":"2","key":"23_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M. Li","year":"2002","unstructured":"M. Li, B. Ma, and L. Wang. On the closest string and substing problems. Journal of the ACM, 49(2):157\u2013171, 2002.","journal-title":"Journal of the ACM"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Ming Li, Bin Ma, and Lusheng Wang. Finding similar regions in many strings. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC\u201999), pages 473\u2013482, 1999.","DOI":"10.1145\/301250.301376"},{"key":"23_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/3-540-45123-4_10","volume-title":"CPM","author":"B. Ma","year":"2000","unstructured":"Bin Ma. A polynomial time approximation scheme for the closest substring problem. In CPM, volume 1848 of LNCS, pages 99\u2013107, 2000."},{"key":"23_CR15","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the Association for Computing Machinery, 25:322\u2013336, 1978.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"3\u20134","key":"23_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1089\/106652700750050826","volume":"7","author":"L. Marsan","year":"2000","unstructured":"L. Marsan and M. F. Sagot. Algorithms for extracting structured motifs using a suffix tree with an application to promoter and regulatory site consensus identification. J Comput Biol, 7(3\u20134):345\u201362, 2000.","journal-title":"J Comput Biol"},{"key":"23_CR17","unstructured":"C. D. Martinez, A. Juan, and F. Casacuberta. Improving classification using median string and nn rules. In Spanish Symp. on Pattern Recognition and Image Analysis, pages 391\u2013395, 2001."},{"key":"23_CR18","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1109\/ICPR.2000.906221","volume":"2","author":"C. D. Martinez-Hinarejos","year":"2000","unstructured":"C. D. Martinez-Hinarejos, A. Juan, and F. Casacuberta. Use of median string for classification. In 15th International Conference on Pattern Recognition, volume 2, pages 907\u2013910, september 2000.","journal-title":"15th International Conference on Pattern Recognition"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Pavel Pevzner. Computational Molecular Biology. MIT Press, 2000.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences, 2003. to appear.","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"23_CR21","unstructured":"J. S. Sim and K. Park. The consensus string problem for a metric is NP-complete. In R. Raman and J. Simpson, editors, Proceedings of the 10th Australasian Workshop On Combinatorial Algorithms, pages 107\u2013113, Perth, WA, Australia, 1999."},{"key":"23_CR22","unstructured":"David J. States and Pankaj Agarwal. Compact encoding strategies for DNA sequence similarity search. In Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology, pages 211\u2013217. AAAI Press, 1996."},{"issue":"1","key":"23_CR23","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM (JACM), 21(1):168\u2013173, 1974.","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"23_CR24","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jagm.1997.0882","volume":"25","author":"L. Wang","year":"1997","unstructured":"L. Wang and D. Gusfield. Improved approximation algorithms for tree alignment. J. Algorithms, 25(2):255\u2013273, 1997.","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44888-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T16:07:51Z","timestamp":1736870871000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44888-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540403111","9783540448884"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44888-8_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]},"assertion":[{"value":"27 May 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}