On-line construction of compact directed acyclic word graphs

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Citations (Scopus)


A Compact Directed Acyclic Word Graph (CDAWG) is a space-efficient text indexing structure, that can be used in several different string algorithms, especially in the analysis of biological sequences. In this paper, we present a new on-line algorithm for its construction, as well as the construction of a CDAWG for a set of strings.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings
EditorsAmihood Amir, Amihood Amir, Gad M. Landau, Gad M. Landau
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540422714, 9783540422716
Publication statusPublished - 2001
Event12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001 - Jerusalem, Israel
Duration: Jul 1 2001Jul 4 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On-line construction of compact directed acyclic word graphs'. Together they form a unique fingerprint.

Cite this