1 citations · 2 across the 6 of their papers we have counts for
6 papers
Quadratic Word Equations with a Linear Side: Polynomial Nielsen Graph Diameter and NP-Completeness
Yuki Yonemoto
The satisfiability problem for word equations asks whether variables can be replaced by words so that the two sides become equal. For regular word equations, in which each variable…
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, Paweł Gawrychowski +2
We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graph…
Simple Linear-time Repetition Factorization
Yuki Yonemoto, Shunsuke Inenaga
A factorization of a string of length is called a repetition factorization of if is a repetition, i.e., is a form of , where i…
Subsequence Matching and LCS with Segment Number Constraints
Yuki Yonemoto, Takuya Mieno, Shunsuke Inenaga +2
The longest common subsequence (LCS) is a fundamental problem in string processing which has numerous algorithmic studies, extensions, and applications. A sequence $u_1, \ldots, u_…
Subsequence Matching and LCS under Cartesian-Tree Equivalence
Taketo Tsujimoto, Yuki Yonemoto, Hiroki Shibata +3
Two strings of the same length are said to Cartesian-tree match (CT-match) if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-tree matching is a natural mod…
Faster Space-Efficient STR-IC-LCS Computation
Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga +1
One of the most fundamental method for comparing two given strings and is the longest common subsequence (LCS), where the task is to find (the length) of an LCS of and…