Campus Event Calendar
Event Entry
What and Who
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Xinkai Shu
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 6 February 2025
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We give a deterministic O(m log^{2/3} n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in comparison-addition model. This is the first result to break the O(m + n log n) time bound of Dijkstra algorithm on sparse graphs, showing that Dijkstra algorithm is not optimal for SSSP.
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
897 027 2575
passcode not visible
logged in users only
Nidhi Rathi, 02/03/2025 13:56 -- Created document.