On the complexity of string folding
UNSPECIFIED. (1996) On the complexity of string folding. DISCRETE APPLIED MATHEMATICS, 71 (1-3). pp. 217-230. ISSN 0166-218XFull text not available from this repository.
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|
|Journal or Publication Title:||DISCRETE APPLIED MATHEMATICS|
|Publisher:||ELSEVIER SCIENCE BV|
|Date:||5 December 1996|
|Number of Pages:||14|
|Page Range:||pp. 217-230|
Actions (login required)