On the Complexity of String Matching for Graphs
From MaRDI portal
Publication:6075757
DOI10.1145/3588334MaRDI QIDQ6075757
Alexandru I. Tomescu, Veli Mäkinen, Massimo Equi, Roberto Grossi
Publication date: 23 October 2023
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
string matchinggraph searchheterogeneous networkslabeled graphsstring searchstrong exponential time hypothesisgraph queryexact pattern matchingvariation graphs
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
- Improved approximate pattern matching on hypertext
- Wheeler graphs: a framework for BWT-based data structures
- On the complexity of approximately matching a string to a directed graph
- The complexity of approximate pattern matching on de Bruijn graphs
- Lengths of words accepted by nondeterministic finite automata
- Indexing hypertext
- On the complexity of sequence to graph alignment
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- Fast Pattern Matching in Strings
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
- Pattern Matching in Hypertext
- On the Hardness and Inapproximability of Recognizing Wheeler Graphs
- Pattern matching in hypertext
- Regular Languages meet Prefix Sorting
- Hardness Results for Intersection Non-Emptiness
- On the complexity of \(k\)-SAT
- Algorithms and complexity on indexing founder graphs
This page was built for publication: On the Complexity of String Matching for Graphs
