scientific article; zbMATH DE number 7561548

DOI10.4230/LIPIcs.ICALP.2019.55MaRDI QIDQ5091210

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

Publication date: 21 July 2022

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

string matchinggraph searchheterogeneouslabeled graphsstring searchstrong exponential time hypothesisgraph queryexact pattern matching

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (16)

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Linear time construction of indexable elastic founder graphs ⋮ The complexity of approximate pattern matching on de Bruijn graphs ⋮ Fast and optimal sequence-to-graph alignment guided by seeds ⋮ On the Complexity of String Matching for Graphs ⋮ Algorithms and complexity on indexing founder graphs ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Elastic founder graphs improved and enhanced ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Succinct representations for (non)deterministic finite automata ⋮ Wheeler languages ⋮ On the complexity of approximately matching a string to a directed graph ⋮ Solving string problems on graphs using the labeled direct product ⋮ On the complexity of recognizing Wheeler graphs

Cites Work

• Unnamed Item
• Improved approximate pattern matching on hypertext
• Intersection non-emptiness and hardness within polynomial time
• Wheeler graphs: a framework for BWT-based data structures
• On the complexity of sequence to graph alignment
• 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
• Pattern Matching in Hypertext
• On the complexity of \(k\)-SAT

This page was built for publication: