Jonathan S. Turner

I&C Journal 1989 Journal Article

Approximation algorithms for the shortest common superstring problem

• Jonathan S. Turner

The object of the shortest common superstring problem (SCS) is to find the shortest possible string that contains every string in a given set as substrings. As the problem is NP-complete, approximation algorithms are of interest. The value of an aproximate solution to SCS is normally taken to be its length, and we seek algorithms that make the length as small as possible. A different measure is given by the sum of the overlaps between consecutive strings in a candidate solution. When considering this measure, the object is to find solutions that make it as large as possible. These two measures offer different ways of viewing the problem. While the two viewpoints are equivalent with respect to optimal solutions, they differ with respect to approximate solutions. We describe several approximation algorithms that produce solutions that are always within a factor of two of optimum with respect to the overlap measure. We also describe an efficient implementation of one of these, using McCreight's compact suffix tree construction algorithm. The worstcase running time is O(m log n) for small alphabets, where m is the sum of the lengths of all the strings in the set and n is the number of strings. For large alphabets, the algorithm can be implemented in O(m log m) time by using Sleator and Tarjan's lexicographic splay tree data structure.

STOC Conference 1983 Conference Paper

Probabilistic Analysis of Bandwidth Minimization Algorithms

• Jonathan S. Turner

FOCS Conference 1982 Conference Paper

Polynomial Time Algorithms for the Min Cut Problem on Degree Restricted Trees

• Moon-Jung Chung
• Fillia Makedon
• Ivan Hal Sudborough
• Jonathan S. Turner

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in O(n(logn)d-2) steps. This also yields an algorithm for determining the black/white pebble demand of degree three trees. A forbidden subgraph characterization is given for degree three trees having cutwidth k. This yields an interesting corollary: for degree three trees, cutwidth is identical to search number.