
The Library
On the complexity of string folding
Tools
Paterson, Michael S. and Przytycka, Teresa (1996) On the complexity of string folding. Discrete Applied Mathematics, Volume 71 (Number 1-3). pp. 217-230. ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/S0166-218X(96)00065-0
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 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: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||
Publisher: | Elsevier Science Ltd. | ||||
ISSN: | 0166-218X | ||||
Official Date: | December 1996 | ||||
Dates: |
|
||||
Volume: | Volume 71 | ||||
Number: | Number 1-3 | ||||
Number of Pages: | 14 | ||||
Page Range: | pp. 217-230 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Version or Related Resource: | Paterson, M.S. and Przytycka, T. (1995). On the complexity of string folding. University of Warwick. Department of Computer Science. (Department of Computer Science research report, 286). | ||||
Related URLs: |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |