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

DOI10.1016/J.TCS.2023.114128MaRDI QIDQ6076352zbMATH OpenOpenAlexFDO

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

Publication date 21 September 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114128

zbMATH Keywords

complexity theoryedit distanceexact pattern matchingFréchet distancegraph queryindexinglower boundsorthogonal vectorsreductionssubtree isomorphism

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

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

Cited in

(1)

• A unifying taxonomy of pattern matching in degenerate strings and founder graphs

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)