
The Library
On the complexity of string folding
Tools
Paterson, Michael S. and Przytycka, Teresa (1995) On the complexity of string folding. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-286.pdf - Other - Requires a PDF viewer. Download (298Kb) | Preview |
Abstract
A fold of a finite string S over a given alphabet is an embedding of S in some fixed infinite grid, such as the square or cubic mesh. The score of a fold is the number of pairs of matching string symbols which are embedded at adjacent grid vertices. Folds of strings and sets of strings in two- and three-dimensional meshes are considered, and the corresponding problems of optimizing the score or achieving a given target score are shown to be NP-hard.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Protein folding -- Mathematical models | ||||
Series Name: | Department of Computer Science research report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Official Date: | 1995 | ||||
Dates: |
|
||||
Number: | Number 286 | ||||
Number of Pages: | 11 | ||||
DOI: | CS-RR-286 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
Grant number: | 7141 (ESPRIT) | ||||
Version or Related Resource: | Paterson, M.S. and Przytycka, T. (1996). On the complexity of string folding. Discrete Applied Mathematics, 71(1-3). pp. 217-230. | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |