
An Almost Optimal Edit Distance Oracle
We consider the problem of preprocessing two strings S and T, of lengths...
read it

FaultTolerant Distance Labeling for Planar Graphs
In faulttolerant distance labeling we wish to assign short labels to th...
read it

A Note on Maximum Integer Flows in Directed Planar Graphs with Vertex Capacities
The most efficient algorithm currently known for computing maximum integ...
read it

Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs
Given an undirected, unweighted planar graph G with n vertices, we prese...
read it

A Note on a Recent Algorithm for Minimum Cut
Given an undirected edgeweighted graph G=(V,E) with m edges and n verti...
read it

Minimum Cut in O(mlog^2 n) Time
We give a randomized algorithm that finds a minimum cut in an undirected...
read it

Compressed Range Minimum Queries
Given a string S of n integers in [0,σ), a range minimum query RMQ(i, j)...
read it

Almost Optimal Distance Oracles for Planar Graphs
We present new tradeoffs between space and querytime for exact distance...
read it

Exact Distance Oracles for Planar Graphs with Failing Vertices
We consider exact distance oracles for directed weighted planar graphs i...
read it

NearOptimal Distance Emulator for Planar Graphs
Given a graph G and a set of terminals T, a distance emulator of G is an...
read it
Shay Mozes
is this you? claim profile