3 citations · 3 across the 4 of their papers we have counts for
6 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…
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
Ran Duan, Jiayi Mao, Xinkai Shu +1
In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O(m\sqrt{\log n \cdot…
Space Complexity of Vertex Connectivity Oracles
Seth Pettie, Thatchaphol Saranurak, Longhui Yin
A -vertex connectivity oracle for undirected is a data structure that, given , reports , where is the pairwise vertex connectivity be…
The Structure of Minimum Vertex Cuts
Seth Pettie, Longhui Yin
In this paper we continue a long line of work on representing the cut structure of graphs. We classify the types minimum vertex cuts, and the possible relationships between multipl…
Non-Mergeable Sketching for Cardinality Estimation
Seth Pettie, Dingyu Wang, Longhui Yin
Cardinality estimation is perhaps the simplest non-trivial statistical problem that can be solved via sketching. Industrially-deployed sketches like HyperLogLog, MinHash, and PCSA…