Does preprocessing help in fast sequence comparisons?

DOI10.1145/3357713.3384300MaRDI QIDQ5144952zbMATH OpenOpenAlexFDO

Authors Elazar Goldenberg, Aviad Rubinstein, Barna Saha

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.09115

zbMATH Keywords

approximation algorithmsedit distancepreprocessing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(5)

• What can and what cannot be inferred from pairwise sequence comparisons?
• Weighted edit distance computation: strings, trees, and Dyck
• Fine-grained hardness for edit distance to a fixed sequence
• Many flavors of edit distance
• Edit distance in near-linear time: it's a constant factor

This page was built for publication: Does preprocessing help in fast sequence comparisons?

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