Dan Gusfield

TCS Journal 2002 Journal Article

Simple and flexible detection of contiguous repeats using a suffix tree

• Jens Stoye
• Dan Gusfield

We study the problem of detecting all occurrences of (primitive) tandem repeats and tandem arrays in a string. We first give a simple time- and space-optimal algorithm to find all tandem repeats, and then modify it to become a time and space-optimal algorithm for finding only the primitive tandem repeats. Both of these algorithms are then extended to handle tandem arrays. The contribution of this paper is both pedagogical and practical, giving simple algorithms and implementations based on a suffix tree, using only standard tree traversal techniques.

SODA Conference 1994 Conference Paper

Reconstructing a History of Recombinations from a Set of Sequences

• John D. Kececioglu
• Dan Gusfield

SODA Conference 1992 Conference Paper

Parametric Optimization of Sequence Alignment

• Dan Gusfield
• K. Balasubramanian
• Dalit Naor

FOCS Conference 1990 Conference Paper

A Fast Algorithm for Optimally Increasing the Edge-Connectivity

• Dalit Naor
• Dan Gusfield
• Charles U. Martel

An undirected, unweighted graph G=(V, E with n nodes, m edges, and connectivity lambda ) is considered. Given an input parameter delta, the edge augmentation problem is to find the smallest set of edges to add to G so that its edge-connectivity is increased by delta. A solution to this problem that runs in time O( delta /sup 2/nm+nF(n)), where F(n) is the time to perform one maximum flow on G, is given. The solution gives the optimal augmentation for every delta ', 1 >

SODA Conference 1990 Conference Paper

Efficient Algorithms for Generalized Cut Trees

• Dan Gusfield
• Dalit Naor