String compression algorithms
John Kenneth Gallant · 1982
This thesis deals with three related problems involving strings, specifically, finding superstrings, the string sequencing problem, and macro compression schemes. In each section, the author shows several natural variants of the problem at hand to be computationally intractable (i.e., NP-complete). He then suggests a number of approximation algorithms and gives bounds on their performance. This work is well motivated, competently executed and constitutes an acceptable Ph.D. thesis. Sections of the work have already been accepted for journal publication.