labeled graphs 1matrix multiplication 1parameterized complexity 1SETH lower bounds 1string matching 1walk length 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.DS2026
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, PaweÅ Gawrychowski +2
The paper classifies the computational complexity of finding a walk with a given pattern in directed graphs whose nodes are labeled by strings, focusing on walks that traverse a bo…
cs.DS2025
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…
cs.DS2025
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_…