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)

Preview

PDF (Department of Computer Science Research Report) WRAP_cs-rr-286.pdf - Other - Requires a PDF viewer. Download (298Kb) | Preview

Request Changes to record.

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 > 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:	Date Event 1995 Completion
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:	Organisation Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads