616 citations
- Ruhr University BochumDE61 papers
- Jagiellonian UniversityPL59 papers
- The University of TokyoJP53 papers
- The University of OsakaJP35 papers
- Forschungszentrum JülichDE28 papers
- Kyushu UniversityJP25 papers
- Tohoku UniversityJP20 papers
- Japan Science and Technology AgencyJP16 papers
- University of ArizonaUS16 papers
- RIKENJP14 papers
- National Institute for Materials ScienceJP13 papers
- Kyoto UniversityJP11 papers
13 papers · 1 filter
Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes
Toshiki Saitoh, Ryo Yoshinaka, Hans L. Bodlaender
For a graph class , the -Edge-Deletion problem asks for a given graph to delete the minimum number of edges from in order to obtain a graph in $\m…
RePair in Compressed Space and Time
Kensuke Sakai, Tatsuya Ohno, Keisuke Goto +3
Given a string of length , the goal of grammar compression is to construct a small context-free grammar generating only . Among existing grammar compression methods, RePa…
Block Palindromes: A New Generalization of Palindromes
Keisuke Goto, Tomohiro I, Hideo Bannai +1
We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are…
Enumerating All Subgraphs without Forbidden Induced Subgraphs via Multivalued Decision Diagrams
Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki +1
We propose a general method performed over multivalued decision diagrams that enumerates all subgraphs of an input graph that are characterized by input forbidden induced subgraphs…
A compressed dynamic self-index for highly repetitive text collections
Takaaki Nishimoto, Yoshimasa Takabatake, Yasuo Tabei
We present a novel compressed dynamic self-index for highly repetitive text collections. Signature encoding is a compressed dynamic self-index for highly repetitive texts and has a…
A Faster Implementation of Online Run-Length Burrows-Wheeler Transform
Tatsuya Ohno, Yoshimasa Takabatake, Tomohiro I +1
Run-length encoding Burrows-Wheeler Transformed strings, resulting in Run-Length BWT (RLBWT), is a powerful tool for processing highly repetitive strings. We propose a new algorith…