3 papers
cs.CC2026
The Complexity of Boolean Connectivity Problem of -Horn Formulas
Takashi Horiyama, Shoon Mineyoshi, Yuto Okura +2
The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the -dimensional hypercube. This problem…
cs.DS2023
Optimal LZ-End Parsing is Hard
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita +3
LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occ…
cs.DS2022
Finding Top-k Longest Palindromes in Substrings
Kazuki Mitani, Takuya Mieno, Kazuhisa Seto +1
Palindromes are strings that read the same forward and backward. Problems of computing palindromic structures in strings have been studied for many years with a motivation of their…