4 papers
A Faster Directed Single-Source Shortest Path Algorithm
Ran Duan, Xiao Mao, Xinkai Shu +1
This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\s…
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao +2
We give a deterministic -time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition m…
Undirected 3-Fault Replacement Path in Nearly Cubic Time
Shucheng Chi, Ran Duan, Benyu Wang +1
Given a graph and two vertices , the -fault replacement path (FRP) problem computes for every set of edges where , the distance from to…
More Asymmetry Yields Faster Matrix Multiplication
Josh Alman, Ran Duan, Virginia Vassilevska Williams +3
We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 20…