The Library
On the complexity of string folding
Tools
Tools
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 |
