Goto, Keisuke

Computing NP-Hard Repetitiveness Measures via MAX-SAT

2021 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation of some of these measures is NP-hard, and straight-forward computation is infeasible …