6 citations · 18 across the 13 of their papers we have counts for
16 papers
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…
RePair Grammars are the Smallest Grammars for Fibonacci Words
Takuya Mieno, Shunsuke Inenaga, Takashi Horiyama
Grammar-based compression is a loss-less data compression scheme that represents a given string by a context-free grammar that generates only . While computing the smallest…
Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions
Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama +3
In this paper, we propose a fast method for exactly enumerating a very large number of all lower cost solutions for various combinatorial problems. Our method is based on backtrack…
Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama +7
A rep-tile is a polygon that can be dissected into smaller copies (of the same size) of the original polygon. A polyomino is a polygon that is formed by joining one or more unit sq…
Finding well-optimized special quasirandom structures with decision diagram
Kohei Shinohara, Atsuto Seko, Takashi Horiyama +1
The advanced data structure of the zero-suppressed binary decision diagram (ZDD) enables us to efficiently enumerate nonequivalent substitutional structures. Not only can the ZDD s…
Efficient Folding Algorithms for Regular Polyhedra
Tonan Kamata, Akira Kadoguchi, Takashi Horiyama +1
We investigate the folding problem that asks if a polygon P can be folded to a polyhedron Q for given P and Q. Recently, an efficient algorithm for this problem has been developed…
Efficient Segment Folding is Hard
Takashi Horiyama, Fabian Klute, Matias Korman +3
We introduce a computational origami problem which we call the segment folding problem: given a set of line-segments in the plane the aim is to make creases along all segments…
Longest Common Subsequence in Sublinear Space
Masashi Kiyomi, Takashi Horiyama, Yota Otachi
We present the first -space polynomial-time algorithm for computing the length of a longest common subsequence. Given two strings of length , the algorithm runs i…
Derivative structure enumeration using binary decision diagram
Kohei Shinohara, Atsuto Seko, Takashi Horiyama +3
A derivative structure is a nonequivalent substitutional atomic configuration derived from a given primitive cell. The enumeration of derivative structures plays an essential role…
Compiling Crossing-free Geometric Graphs with Connectivity Constraint for Fast Enumeration, Random Sampling, and Optimization
Yu Nakahata, Takashi Horiyama, Shin-ichi Minato +1
Given points in the plane, we propose algorithms to compile connected crossing-free geometric graphs into directed acyclic graphs (DAGs). The DAGs allow efficient counting, enu…
Geodesic Folding of Tetrahedron
Seri Nishimoto, Takashi Horiyama, Tomohiro Tachi
In this work, we show the geometric properties of a family of polyhedra obtained by folding a regular tetrahedron along regular triangular grids. Each polyhedron is identified by a…
Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration
Yu Nakahata, Jun Kawahara, Takashi Horiyama +1
Given graphs and , we propose a method to implicitly enumerate topological-minor-embeddings of in using decision diagrams. We show a useful application of our method…
Decomposing a Graph into Unigraphs
Takashi Horiyama, Jun Kawahara, Shin-ichi Minato +1
Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. There are many subclasses of unigraphs such as threshold graphs, split matrogenic graphs, m…
Rigid Foldability is NP-Hard
Hugo Akitaya, Erik D. Demaine, Takashi Horiyama +3
In this paper, we show that deciding rigid foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from Partition, and that deciding rigid foldabil…
Enumerating Cryptarithms Using Deterministic Finite Automata
Yuki Nozaki, Diptarama Hendrian, Ryo Yoshinaka +2
A cryptarithm is a mathematical puzzle where given an arithmetic equation written with letters rather than numerals, a player must discover an assignment of numerals on letters tha…
Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5
We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…