Skip to Main content Skip to Navigation
Book sections

On Compact Directed Acyclic Word Graphs

Abstract : The Directed Acyclic Word Graph (DAWG) is a space-efficient data structure to treat and analyze repetitions in a text, especially in DNA genomic sequences. Here, we consider the Compact Directed Acyclic Word Graph of a word. We give the first direct algorithm to construct it. It runs in time linear in the length of the string on a fixed alphabet. Our implementation requires half the memory space used by DAWGs.
Document type :
Book sections
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 6:35:25 PM
Last modification on : Saturday, January 15, 2022 - 3:57:31 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:45 AM


Files produced by the author(s)


  • HAL Id : hal-00620801, version 1



Maxime Crochemore, Renaud Vérin. On Compact Directed Acyclic Word Graphs. Mycielski J., Rozenberg G., Salomaa A. Structures in Logic and Computer Science, 1261, Springer-Verlag, pp.192-211, 1997, LNCS. ⟨hal-00620801⟩



Record views


Files downloads