Solving string problems on graphs using the labeled direct product

DOI10.1007/s00453-022-00989-xOpenAlexW4283805622MaRDI QIDQ2088591

Alexandru I. Tomescu, Nicola Rizzo, Alberto Policriti

Publication date: 6 October 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00989-x

zbMATH Keywords

graph algorithmlongest common substringmotif discoverystring algorithmlongest repeated substringfine-grained complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• The suffix tree of a tree and minimizing sequential transducers
• On the degree of ambiguity of finite automata
• Wheeler graphs: a framework for BWT-based data structures
• Wheeler languages
• Conditional lower bounds for space/time tradeoffs
• On the complexity of sequence to graph alignment
• A new algorithm for optimal 2-constraint satisfaction and its implications
• GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS
• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• Succinct de Bruijn Graphs
• Pattern Matching in Hypertext
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Ambiguity, Nondeterminism and State Complexity of Finite Automata
• Unambiguity in Automata Theory
• Boolean Operations on Graphs.
• Ambiguity in Graphs and Expressions
• Pattern Discovery in Bioinformatics

This page was built for publication: Solving string problems on graphs using the labeled direct product