On Hardness of Several String Indexing Problems

DOI10.1007/978-3-319-07566-2_25MaRDI QIDQ5165610zbMATH OpenOpenAlexFDO

Authors Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, Sharma V. Thankachan

Publication date 30 June 2014

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-07566-2_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• On hardness of several string indexing problems
• Automata, Languages and Programming
• String indexes and the proofs of the KRT
• On the kernelization complexity of string problems
• On the kernelization complexity of string problems
• Multivariate algorithmics for NP-hard string problems
• On hardness of jumbled indexing
• scientific article; zbMATH DE number 1336330
• On the far from most string problem, one of the hardest string selection problems
• On the Exact Complexity of String Matching: Upper Bounds

Cited in

(13)

• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Compact indexes for flexible top-k
• On hardness of several string indexing problems
• On the Cost of Interchange Rearrangement in Strings
• Space-efficient indexes for forbidden extension queries
• Time-optimal top-k document retrieval
• Fast set intersection and two-patterns matching
• Ranked document retrieval with forbidden pattern
• Fast set intersection and two-patterns matching
• Ranked document retrieval for multiple patterns
• Data structure lower bounds for document indexing problems
• Forbidden patterns
• Cross-document pattern matching

This page was built for publication: On Hardness of Several String Indexing Problems

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