| 1 |
The Labeled Direct Product Optimally Solves String Problems on Graphs ...
|
|
|
|
Abstract:
Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching, longest common substring, matching statistics, and longest repeated substring. Recent lines of research focused on extending some of these problems to vertex-labeled graphs, although using ad-hoc approaches which in some cases do not generalize to all input graphs. In the absence of a ubiquitous tool like the suffix tree for labeled graphs, we introduce the labeled direct product of two graphs as a general tool for obtaining optimal algorithms: we obtain conceptually simpler algorithms for the quadratic problems of string matching (SMLG) and longest common substring (LCSP) in labeled graphs. Our algorithms are also more efficient, since they run in time linear in the size of the labeled product graph, which may be smaller than quadratic for some inputs, and their run-time is predictable, because the size of the labeled direct product graph can be precomputed ... : 19 pages, 8 figures ...
|
|
Keyword:
Computational Complexity cs.CC; Data Structures and Algorithms cs.DS; FOS Computer and information sciences
|
|
URL: https://dx.doi.org/10.48550/arxiv.2109.05290
https://arxiv.org/abs/2109.05290
|
|
BASE
|
|
Hide details
|
|
|
|
|
