<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>6986</REFNUM><AUTHORS><AUTHOR>Middendorf,M.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2004</YEAR><TITLE>Combined Super-/Substring and Super-/Subsequence Problems</TITLE><PLACE_PUBLISHED>Theoretical Computer Science, volume 320</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>247-267</PAGES><ISBN>0304-3975</ISBN><LABEL>Middendorf:2004:6986</LABEL><ABSTRACT>Super-/substring problems and super-/subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. Here we investigate the complexity of a new type of such problem that forms a combination of a super-/substring and a super-/subsequence problem. Moreover we introduce different types of minimal superstring and maximal substring problems. In particular, we consider the following problems: given a set L of strings and a string S, (i) find a minimal superstring (or maximal substring) of L that is also a supersequence (or a subsequence) of S, (ii) find a minimal supersequence (or maximal subsequence) of L that is also a superstring (or a substring) of S. In addition some non-super-/non-substring and non-super-/non-subsequence variants are studied. We obtain several NP-hardness or even MAX SNP-hardness results and also identify types of "weak minimal" superstrings and "weak maximal" substrings for which (i) is polynomial-time solvable.</ABSTRACT><URL>http://dx.doi.org/doi:10.1016/j.tcs.2004.02.001</URL></RECORD></RECORDS></XML>