The Library
On the complexity of string folding
Tools
Tools
Tools
UNSPECIFIED (1996) On the complexity of string folding. DISCRETE APPLIED MATHEMATICS, 71 (1-3). pp. 217-230. ISSN 0166-218X
Full text not available from this repository.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 |
| Journal or Publication Title: | DISCRETE APPLIED MATHEMATICS |
| Publisher: | ELSEVIER SCIENCE BV |
| ISSN: | 0166-218X |
| Date: | 5 December 1996 |
| Volume: | 71 |
| Number: | 1-3 |
| Number of Pages: | 14 |
| Page Range: | pp. 217-230 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/18176 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
