Ran Duan

collaborators

2 papers

cs.DS2025

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Ran Duan, Jiayi Mao, Xiao Mao +2

We give a deterministic $O (m lo g^{2/3} n)$ -time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition m…

cs.DS2024

Undirected 3-Fault Replacement Path in Nearly Cubic Time

Shucheng Chi, Ran Duan, Benyu Wang +1

Given a graph $G = (V, E)$ and two vertices $s, t \in V$ , the $f$ -fault replacement path ( $f$ FRP) problem computes for every set of edges $F$ where $∣ F ∣ \leq f$ , the distance from $s$ to…