Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
From MaRDI portal
Publication:6076352
DOI10.1016/j.tcs.2023.114128OpenAlexW3010580865MaRDI QIDQ6076352
Alexandru I. Tomescu, Massimo Equi, Veli Mäkinen
Publication date: 21 September 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114128
lower boundsreductionsindexingorthogonal vectorscomplexity theoryFréchet distanceedit distancegraph queryexact pattern matchingsubtree isomorphism
Cites Work
- 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
- Can we compute the similarity between surfaces?
- A faster algorithm computing string edit distances
- Wheeler graphs: a framework for BWT-based data structures
- Comparison of distance measures for planar curves
- Efficient pattern matching in elastic-degenerate strings
- Indexing hypertext
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Compressing and indexing labeled trees, with applications
- Indexing compressed text
- Jewels of Stringology
- New text indexing functionalities of the compressed suffix arrays
- Subtree Isomorphism Revisited
- Threesomes, Degenerates, and Love Triangles
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- On the Hardness and Inapproximability of Recognizing Wheeler Graphs
- Pattern matching in hypertext
- On-line pattern matching on similar texts
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
- Faster Online Elastic Degenerate String Matching
- Regular Languages meet Prefix Sorting
- Indexing Variation Graphs
- Lower bounds for text indexing with mismatches and differences
- More Applications of the Polynomial Method to Algorithm Design
- Distance Oracles beyond the Thorup--Zwick Bound
- Fréchet Distance for Curves, Revisited
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- On the complexity of \(k\)-SAT
- On the Complexity of String Matching for Graphs
This page was built for publication: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
