2 citations · 3 across the 6 of their papers we have counts for
5 papers · 1 filter
Output-Sensitive Construction of CDAWGs from BWT-Runs
Yuta Tsuruzono, Hiroki Arimura, Shunsuke Inenaga
The compact directed acyclic word graph (CDAWG) of a string can be viewed in two equivalent ways: as the edge-compacted DAWG of the string, and as the DAG obtained from the suffix…
Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars
Taiki Kaneda, Hiroki Arimura, Shunsuke Inenaga
We study fully persistent dynamic strings with equality and longest common extension (LCE) queries. Straightforward full persistence is problematic for the splay-based FeST structu…
Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura +2
A string is said to be a minimal absent word (MAW) for a string if does not occur in and any proper substring of occurs in . We focus on non-trivial MAWs whi…
Minimum Consistent Subset for Trees Revisited
Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi +2
In a vertex-colored graph , a subset is said to be consistent if every vertex has a nearest neighbor in with the same color. The problem of computin…
Cartesian Tree Subsequence Matching
Tsubasa Oizumi, Takeshi Kai, Takuya Mieno +2
Park et al. [TCS 2020] observed that the similarity between two (numerical) strings can be captured by the Cartesian trees: The Cartesian tree of a string is a binary tree recursiv…