Debarati Das

activity

20182023

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2023

Weighted Edit Distance Computation: Strings, Trees and Dyck

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2

Given two strings of length $n$ over alphabet $Σ$ , and an upper bound $k$ on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes…

cs.DS2022

$O ~ (n + poly (k))$ -time Algorithm for Bounded Tree Edit Distance

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3

Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…

cs.DS2021

A Linear-Time $n^{0.4}$ -Approximation for Longest Common Subsequence

Karl Bringmann, Vincent Cohen-Addad, Debarati Das

We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length $n$ . While a simple quadratic algorithm has been known for the problem fo…

Weighted Edit Distance Computation: Strings, Trees and Dyck

O~(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

A Linear-Time n0.4-Approximation for Longest Common Subsequence

$O ~ (n + poly (k))$ -time Algorithm for Bounded Tree Edit Distance

A Linear-Time $n^{0.4}$ -Approximation for Longest Common Subsequence