Oren Weimann

activity

20062026

most citedAn O(n^3)-Time Algorithm for Tree Edit Distance

206 citations · 303 across the 29 of their papers we have counts for

collaborators

Showing 2019Show all

3 papers · 1 filter

cs.DS2019

Minimum Cut in $O (m lo g^{2} n)$ Time

Paweł Gawrychowski, Shay Mozes, Oren Weimann

We give a randomized algorithm that finds a minimum cut in an undirected weighted $m$ -edge $n$ -vertex graph $G$ with high probability in $O (m lo g^{2} n)$ time. This is the first imp…

cs.DS2019

Compressed Range Minimum Queries

Paweł Gawrychowski, Seungbum Jo, Shay Mozes +1

Given a string $S$ of $n$ integers in $[0, σ)$ , a range minimum query RMQ $(i, j)$ asks for the index of the smallest integer in $S [i \dots j]$ . It is well known that the problem can…

cs.DS2019

Top Tree Compression of Tries

Philip Bille, Inge Li Gørtz, Paweł Gawrychowski +2

We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supp…

Minimum Cut in O(mlog2n) Time

Compressed Range Minimum Queries

Top Tree Compression of Tries

Minimum Cut in $O (m lo g^{2} n)$ Time