research
∙
07/14/2023
Õptimal Fault-Tolerant Reachability Labeling in Planar Graphs
We show how to assign labels of size Õ(1) to the vertices of a directed ...
share
research
∙
05/04/2023
What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs?
The Voronoi diagrams technique was introduced by Cabello to compute the ...
research
∙
02/13/2023
Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
We give an Õ(n^2) time algorithm for computing the exact Dynamic Time Wa...
research
∙
02/10/2022
Improved Compression of the Okamura-Seymour Metric
Let G=(V,E) be an undirected unweighted planar graph. Consider a vector ...
research
∙
08/19/2021
A Conditional Lower Bound for Episode Matching
Given two strings S and P, the Episode Matching problem is to compute th...
research
∙
03/04/2021
An Almost Optimal Edit Distance Oracle
We consider the problem of preprocessing two strings S and T, of lengths...
research
∙
02/14/2021
Fault-Tolerant Distance Labeling for Planar Graphs
In fault-tolerant distance labeling we wish to assign short labels to th...
research
∙
08/05/2020
A Note on a Recent Algorithm for Minimum Cut
Given an undirected edge-weighted graph G=(V,E) with m edges and n verti...
research
∙
02/18/2020
On the Fine-Grained Complexity of Parity Problems
We consider the parity variants of basic problems studied in fine-graine...
research
∙
11/04/2019
Minimum Cut in O(mlog^2 n) Time
We give a randomized algorithm that finds a minimum cut in an undirected...
research
∙
02/12/2019
Compressed Range Minimum Queries
Given a string S of n integers in [0,σ), a range minimum query RMQ(i, j)...
research
∙
02/06/2019
Top Tree Compression of Tries
We present a compressed representation of tries based on top tree compre...
research
∙
11/05/2018
Almost Optimal Distance Oracles for Planar Graphs
We present new tradeoffs between space and query-time for exact distance...
research
∙
07/04/2018
Near-Optimal Distance Emulator for Planar Graphs
Given a graph G and a set of terminals T, a distance emulator of G is an...
research
∙
02/15/2018
