Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui. Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. DOI: 10.1145/3717823.3718179
We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.
*F.I.C calls for attention regarding this publication about the potential applications in the related research fields.
*F.I.C calls for attention regarding this publication about the potential applications in the related research fields.
See Also:
Latest articles in those days:
- T cell help is a limiting factor for rare anti-influenza memory B cells to reenter germinal centers and generate potent broadly neutralizing antibodies 1 days ago
- Wild birds drive the introduction, maintenance, and spread of H5N1 clade 2.3.4.4b high pathogenicity avian influenza viruses in Spain, 2021-2022 1 days ago
- [preprint]FluNexus: a versatile web platform for antigenic prediction and visualization of influenza A viruses 1 days ago
- Salpingitis and multiorgan lesions caused by highly pathogenic avian influenza A(H5N1) virus in a cat associated with consumption of recalled raw milk in California 1 days ago
- Detection of highly pathogenic avian influenza A(H5N1) virus 2.3.4.4b in alpacas 1 days ago
[Go Top] [Close Window]
