Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
NP-Completeness for the Space-Optimality of Double-Array Tries
Hideo Bannai, Keisuke Goto, Shunsuke Kanda +1
Indexing a set of strings for prefix search or membership queries is a fundamental task with many applications such as information retrieval or database systems. A classic abstract…
cs.DS2022
Computing NP-hard Repetitiveness Measures via MAX-SAT
Hideo Bannai, Keisuke Goto, Masakazu Ishihata +3
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation o…