Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

lower bounds complexity theory edit distance reductions indexing graph query exact pattern matching orthogonal vectors subtree isomorphism Fréchet distance

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

Compressing and indexing labeled trees, with applications
Indexing compressed text
Threesomes, degenerates, and love triangles
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
On the complexity of \(k\)-SAT
A new algorithm for optimal 2-constraint satisfaction and its implications
Jewels of Stringology
A faster algorithm computing string edit distances
Distance oracles beyond the Thorup-Zwick bound
COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
Comparison of distance measures for planar curves
New text indexing functionalities of the compressed suffix arrays
Fréchet Distance for Curves, Revisited
Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
Wheeler graphs: a framework for BWT-based data structures
Degenerate string comparison and applications
Even faster elastic-degenerate string matching via fast matrix multiplication
Title not available (Why is that?)
Pattern matching in hypertext
On-line pattern matching on similar texts
Fully functional suffix trees and optimal text searching in BWT-runs bounded space
Orthogonal vectors indexing
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
Title not available (Why is that?)
An Efficient Elastic-Degenerate Text Index? Not Likely
Linear time construction of indexable founder block graphs
Can we compute the similarity between surfaces?
Subtree isomorphism revisited
Title not available (Why is that?)
On the Complexity of String Matching for Graphs
On the Hardness and Inapproximability of Recognizing Wheeler Graphs
On some fine-grained questions in algorithms and complexity
Indexing hypertext

This page was built for publication: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

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