- AutorIn
- Martin Middendorf
- David F. Manlove
- Titel
- Combined super-/substring and super-/subsequence problems
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:15-qucosa2-320300
- Quellenangabe
- Theoretical Computer Science Verlag: Elsevier
Erscheinungsjahr: 2004
Jahrgang: 320
Heft: 2-3
Seiten: 247-267
ISSN: 0304-3975 - Erstveröffentlichung
- 2004
- Abstract (EN)
- 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.
- Freie Schlagwörter (DE)
- Informatics, Computer science
- Klassifikation (DDC)
- 004
- Version / Begutachtungsstatus
- publizierte Version / Verlagsversion
- URN Qucosa
- urn:nbn:de:bsz:15-qucosa2-320300
- Veröffentlichungsdatum Qucosa
- 25.10.2018
- Dokumenttyp
- Artikel
- Sprache des Dokumentes
- Englisch