6 papers
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 and an arbitrarily larg…
A Scaling Algorithm for Weighted -Factors in General Graphs
Ran Duan, Haoqing He, Tianyi Zhang
We study the maximum weight perfect -factor problem on any general simple graph with positive integral edge weights , and , . When we have a functio…
Approximate Distance Oracles Subject to Multiple Vertex Failures
Ran Duan, Yong Gu, Hanlin Ren
Given an undirected graph of vertices and edges with weights in , we construct vertex sensitive distance oracles (VSDO), which are data structures that pre…
Faster Algorithms for All Pairs Non-decreasing Paths Problem
Ran Duan, Ce Jin, Hongxun Wu
In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time $\tilde{O}(n^{\frac{3 + ω}…
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs
Ran Duan, Kaifeng Lyu, Hongxun Wu +1
In a directed graph with a capacity on every edge, a \emph{bottleneck path} (or \emph{widest path}) between two vertices is a path maximizing the minimum capacity of edge…
Improved distance sensitivity oracles via tree partitioning
Ran Duan, Tianyi Zhang
We introduce an improved structure of distance sensitivity oracle (DSO). The task is to pre-process a non-negatively weighted graph so that a data structure can quickly answer repl…