Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
We present the first dynamic algorithms for Dyck and tree edit distances with subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a well-pa…
cs.DS2025
Fitting Tree Metrics and Ultrametrics in Data Streams
Amir Carmel, Debarati Das, Evangelos Kipouridis +1
Fitting distances to tree metrics and ultrametrics are two widely used methods in hierarchical clustering, primarily explored within the context of numerical taxonomy. Given a posi…