scientific article; zbMATH DE number 7561514
From MaRDI portal
Publication:5091170
DOI10.4230/LIPIcs.ICALP.2019.21MaRDI QIDQ5091170
Paweł Gawrychowski, Giovanna Rosone, Solon P. Pissis, Giulia Bernardini, Nadia Pisanti
Publication date: 21 July 2022
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
fast Fourier transformpattern matchingstring algorithmsmatrix multiplicationelastic-degenerate string
Related Items (9)
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ On the Complexity of String Matching for Graphs ⋮ Algorithms and complexity on indexing founder graphs ⋮ Elastic-degenerate string matching with 1 error ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Approximate pattern matching on elastic-degenerate text ⋮ Comparing Degenerate Strings ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple deterministic wildcard matching
- Fast pattern-matching on indeterminate strings
- Computing dominances in \(E^ n\)
- General context-free recognition in less than cubic time
- An improved combinatorial algorithm for Boolean matrix multiplication
- A data structure for dynamic trees
- Efficient pattern matching in elastic-degenerate strings
- On hardness of several string indexing problems
- Efficient determination of the transitive closure of a directed graph
- NR‐grep: a fast and flexible pattern‐matching tool
- Finding a maximum weight triangle in n 3-Δ time, with applications
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Constructing Efficient Dictionaries in Close to Sorting Time
- Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
- Verifying candidate matches in sparse and wildcard matching
- Generalized String Matching
- Multidimensional binary search trees used for associative searching
- Fast Pattern Matching in Strings
- Two-way string-matching
- Faster algorithms for string matching with k mismatches
- Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
- On-line pattern matching on similar texts
- Faster Online Elastic Degenerate String Matching
- Pattern Matching on Elastic-Degenerate Text with Errors
- Regularity Lemmas and Combinatorial Algorithms
- Uniqueness Theorems for Periodic Functions
- Internal Pattern Matching Queries in a Text and Applications
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Hardness of RNA Folding Problem With Four Symbols.
- Color-Distance Oracles and Snippets
- Multiplying matrices faster than coppersmith-winograd
- Algorithms on Strings
- Algorithms – ESA 2004
This page was built for publication:
