<%@ page language="java" contentType="text/html" %>
<%-- Include common initialisation code --%>
<%@ include file="/arch/common.jsp" %>
<%-- The current tab --%>
<% String currentTab = "Research"; %>
<%-- Content of navigation pane --%>
<%@ include file="nav.jsp" %>
<% showCurrentLink=true; %>
<%-- Current navigation location --%>
<% String currentNav = "Reports and Theses"; %>
<%-- Include the code for the document header --%>
<%@ include file="/arch/header.jsp" %>
Research Report CS-RR-286
<%-- Include the code for the lines and navigation --%>
<%@ include file="/arch/middle.jsp" %>
M.S. Paterson and T. Przytycka,
On the Complexity of String Folding
(May 1, 1995).
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.
Download
cs-rr-286.ps.gz
<%-- Include the code for the document footer --%>
<%@ include file="/arch/footer.jsp" %>