Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, Barna Saha +3
The tree edit distance (TED) between two rooted ordered trees with nodes labeled from an alphabet is the minimum cost of transforming one tree into the other by a sequence…
cs.DS2024
3SUM in Preprocessed Universes: Faster and Simpler
Shashwat Kasliwal, Adam Polak, Pratyush Sharma
We revisit the 3SUM problem in the \emph{preprocessed universes} setting. We present an algorithm that, given three sets , , of integers, preprocesses them in quadrat…
cs.DS2023
Connectivity Oracles for Predictable Vertex Failures
Bingbing Hu, Evangelos Kosinas, Adam Polak
The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous…