Hanlin Ren

collaborators

3 papers

cs.DS2021

Maintaining Exact Distances under Multiple Edge Failures

Ran Duan, Hanlin Ren

We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph $G = (V, E)$ and an arbitrarily larg…

cs.DS2021

Constructing a Distance Sensitivity Oracle in $O (n^{2.5794} M)$ Time

Yong Gu, Hanlin Ren

We continue the study of distance sensitivity oracles (DSOs). Given a directed graph $G$ with $n$ vertices and edge weights in ${1, 2, \dots, M}$ , we want to build a data structu…

cs.DS2020

Approximate Distance Oracles Subject to Multiple Vertex Failures

Ran Duan, Yong Gu, Hanlin Ren

Given an undirected graph $G = (V, E)$ of $n$ vertices and $m$ edges with weights in $[1, W]$ , we construct vertex sensitive distance oracles (VSDO), which are data structures that pre…

Maintaining Exact Distances under Multiple Edge Failures

Constructing a Distance Sensitivity Oracle in O(n2.5794M) Time

Approximate Distance Oracles Subject to Multiple Vertex Failures

Constructing a Distance Sensitivity Oracle in $O (n^{2.5794} M)$ Time