Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen

Bibliography

BFC00 (BFC00.pdf)

Michael A. Bender and Martin Farach-Colton, The lca problem revisited, Latin American Theoretical INformatics, may 2000, pp. 88-94.

BYG96 (BYG96.pdf)

Ricardo A. Baeza-Yates and Gaston H. Gonnet, Fast text searching for regular expressions or automaton searching on tries, Journal of the ACM 43 (1996), no. 6, 915-936.

CL94 (CL94.pdf)

William I. Chang and Eugene L. Lawler, Sublinear approximate string matching and biological applications, Algorithmica 12 (1994), 327-344.

FGD95 (FGD95.pdf)

Philippe Flajolet, Xavier Gourdon, and Philippe Dumas, Mellin transforms and asymptotics: Harmonic sums, Theoretical Comp. Science 144 (1995), no. 1-2, 3-58.

FS86 (FS86.pdf)

Philippe Flajolet and Robert Sedgewick, Digital search trees revisited, SIAM J. Comput. 15 (1986), no. 3, 748-767.

FS95 (FS95.pdf)

Philippe Flajolet and Robert Sedgewick, Mellin transforms and asymptotics: Finite differences and rice's integral, Theoretical Computer Science 144 (1995), no. 1-2, 101-124.

FS98 (FS98.pdf)

A. Frieze and W. Szpankowski, Greedy algorithms for the shortest common superstring that are asymptotically optimal, Algorithmica 21 (1998), 21-36.

GO81 (GO81.pdf)

L. J. Guibas and A. M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. of Combinatorial Theory, Series A 30 (1981), no. 183-208.

Gus97 (Ch. 6 Gus97-6.pdf, Ch. 8 Gus97-8.pdf)

Dan Gusfield, Algorithms on strings, trees, and sequences: Comp. science and computational biology, Cambridge University Press, 1997.

GV00 (GV00.pdf)

Roberto Grossi and Jeffry Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching, 32nd Symp. on Theory of Comput., 2000, pp. 397-406.

KS03 (KS03.pdf)

Juha Kärkkäinen and Peter Sanders, Simple linear work suffix array construction, Proc. 30th Int. Colloq. on Automata, Languages and Programming (ICALP), LNCS, vol. 2719, Springer, 2003, pp. 943-955.

MM93 (MM93.pdf)

Udi Manber and Gene Myers, Suffix arrays: A new method for on-line string searches, SIAM J. Comput. 22 (1993), no. 5, 935-948.

NBY00 (NBY00.pdf)

G. Navarro and R. Baeza-Yates, A hybrid indexing method for approximate string matching, Journal of Discrete Algorithms (JDA) 1 (2000), no. 1, 205-209, Special issue on Matching Patterns.

RS98a (RS98a.pdf)

M. Regnier and W. Szpankowski, Complexity of sequential pattern matching algorithms, Proc. RANDOM, LNCS, vol. 1518, Springer, 1998, pp. 187-199.

RS98b (RS98b.pdf)

Mireille Regnier and Wojciech Szpankowski, On pattern frequency occurrences in a markovian sequence, Algorithmica 22 (1998), 631-649.

Sad00 (Sad00.pdf)

Kunihiko Sadakane, Compressed text databases with efficient query algorithms based on the compressed suffix array, Proc. ISAAC, LNCS, vol. 1969, Springer, 2000, pp. 410-421.

Szp93 (Szp93.pdf)

Wojciech Szpankowski, Asymptotic properties of data compression and suffix trees, IEEE Transactions on Information Theory 39 (1993), no. 5, 1647-1659.

Szp00 (Preliminary version on-line at Wojciech Szpankowskis hompage: Click here.)

to3em, Average case analysis of algorithms on sequences, 1 ed., Wiley-Interscience, 2000.

Ukk95 (Ukk95.pdf)

E. Ukkonen, On-line construction of suffix trees, Algorithmica 14 (1995), 249-260.