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

exact pattern matchinggraph querygraph searchheterogeneous networkslabeled graphsstring matchingstring searchstrong exponential time hypothesisvariation 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

• 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
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• Improved approximate pattern matching on hypertext
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Indexing hypertext
• Lengths of words accepted by nondeterministic finite automata
• 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
• On the complexity of string matching for graphs
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• 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

(18)

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

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)