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:
- The evolution and transmission dynamics of H3N2 influenza virus identified in a respiratory disease outbreak in companion dogs in Alabama, USA 6 hours ago
- Structural and functional characterization of hemagglutinin E190D and Q226H minor variants in human H5N1 A/British Columbia/PHL-2032/2024 6 hours ago
- Spatial risk factors associated with outbreaks of highly pathogenic avian influenza in Pennsylvania’s commercial poultry farms 6 hours ago
- [preprint]H9N2 avian influenza virus in Bangladesh: three genetically distinct co-circulating subgroups retain a largely conserved antigenic phenotype 6 hours ago
- [preprint]Endogenous serine proteases in MDCK sublines support trypsin-independent influenza A virus replication 6 hours ago
[Go Top] [Close Window]


