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:
- [preprint]The mammalian-adaptive PB2-E627K substitution preserves viral fitness of clade 2.3.4.4b H5N1 HPAIV in birds 9 hours ago
- Mallard super-shedders of avian influenza exhibit distinct cloacal microbial abundance profiles 13 hours ago
- A digitally immune-optimized influenza vaccine broadly neutralizes swine and human H1N1 influenza viruses and protects from heterologous challenge 13 hours ago
- Associations between vaccine misinformation and influenza vaccine uptake: a population-based interrupted time-series study in China 13 hours ago
- Infection and transmission dynamics of bovine and human influenza A H5N1 viruses in mouse and hamster models 14 hours ago
[Go Top] [Close Window]
