3 papers
cs.DS2026
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…
cs.DS2025
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…
cs.DS2025
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…