On the Complexity of String Matching for Graphs

DOI10.1145/3588334MaRDI QIDQ6075757zbMATH OpenWikidataFDO

Authors Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu, Roberto Grossi

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1145/3588334

zbMATH Keywords

string matchinggraph searchheterogeneous networkslabeled graphsstring searchstrong exponential time hypothesisgraph queryexact pattern matchingvariation graphs

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• On the complexity of string matching for graphs
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Complexity issues of string to graph approximate matching
• On the complexity of approximately matching a string to a directed graph
• The complexity of approximate pattern matching on de Bruijn graphs

Cites work

• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 7561548 (Why is no real title available?)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Algorithms and complexity on indexing founder graphs
• Degenerate string comparison and applications
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Fast Pattern Matching in Strings
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Hardness results for intersection non-emptiness
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Improved approximate pattern matching on hypertext
• Indexing hypertext
• Lengths of words accepted by nondeterministic finite automata
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• On the complexity of k-SAT
• On the complexity of approximately matching a string to a directed graph
• On the complexity of sequence to graph alignment
• Pattern Matching in Hypertext
• Pattern matching in hypertext
• Regular Languages meet Prefix Sorting
• The complexity of approximate pattern matching on de Bruijn graphs
• Wheeler graphs: a framework for BWT-based data structures

Cited in

(15)

• Finding maximal exact matches in graphs
• Prefix sorting DFAs: a recursive algorithm
• Elastic-degenerate string comparison
• An external-memory algorithm for string graph construction
• Algorithms and complexity on indexing founder graphs
• Complexity results and algorithms for representing paths in digraphs
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Elastic-degenerate string matching with 1 error or mismatch
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• String graphs. II: Recognizing string graphs is NP-hard
• A Myhill-Nerode theorem for generalized automata, with applications to pattern matching and compression
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• Solving string problems on graphs using the labeled direct product
• Chaining of maximal exact matches in graphs

This page was built for publication: On the Complexity of String Matching for Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075757)