Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence

DOI10.1137/1.9781611975482.100zbMath1431.68171OpenAlexW4240117647MaRDI QIDQ5236284

Xiaorui Sun, Saeed Seddighin, Mohammad Taghi Hajiaghayi

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.100

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (3)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Maliciously secure massively parallel computation for all-but-one corruptions

This page was built for publication: Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence