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
∙
01/27/2021
A Note on Maximum Integer Flows in Directed Planar Graphs with Vertex Capacities
The most efficient algorithm currently known for computing maximum integ...
research
∙
09/30/2020
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs
Given an undirected, unweighted planar graph G with n vertices, we prese...
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
∙
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
∙
11/05/2018
Almost Optimal Distance Oracles for Planar Graphs
We present new tradeoffs between space and query-time for exact distance...
research
∙
07/16/2018
Exact Distance Oracles for Planar Graphs with Failing Vertices
We consider exact distance oracles for directed weighted planar graphs i...
research
∙
07/04/2018
