Partial permutations comparison, maintenance and applications

DOI10.1016/J.TCS.2025.115433MaRDI QIDQ6914030zbMATH OpenFDO

Authors Avivit Levy, Ely Porat, B. R. Shalom

Publication date 17 October 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115433

zbMATH Keywords

color transformationdictionary matching with gapsgenes comparisonparameterized matchingpartial permutationsSETH

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Data structures (68P05) Combinatorics in computer science (68R05) Algorithms on strings (68W32)

Cites work

• A combinatorial proof of the Cayley-Hamilton theorem
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• A theory of parameterized pattern matching
• An Erdős--Ko--Rado theorem for partial permutations
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Dictionary matching and indexing with errors and don't cares
• Dictionary matching with a few gaps
• Dictionary matching with one gap
• DNA Computing
• Faster Online Matrix-Vector Multiplication
• Genome Rearrangements and Sorting by Reversals
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2086643 (Why is no real title available?)
• scientific article; zbMATH DE number 1834684 (Why is no real title available?)
• Introduction to algorithms.
• LCS approximation via embedding into locally non-repetitive strings
• Mind the gap!
• Mind the gap: essentially optimal algorithms for online dictionary matching with one gap
• More applications of the polynomial method to algorithm design
• On some fine-grained questions in algorithms and complexity
• On the complexity of k-SAT
• Online parameterized dictionary matching with one gap
• Online recognition of dictionary with one gap
• Overlap-freeness in infinite partial words
• Parameterized dictionary matching and recognition with one gap
• Partial words and a theorem of Fine and Wilf
• Pattern avoidance in partial permutations
• Ranking and unranking permutations in linear time
• Restricted patience sorting and barred pattern avoidance
• Square-free partial words
• String rearrangement metrics: a survey
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
• Unavoidable sets of partial words
• Which problems have strongly exponential complexity?

This page was built for publication: Partial permutations comparison, maintenance and applications

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