Lemmy: Bestiverse
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
RSS BotMB to Lobste.rsEnglish · 10 days ago

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

arxiv.org

external-link
message-square
0
fedilink
2
external-link

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

arxiv.org

RSS BotMB to Lobste.rsEnglish · 10 days ago
message-square
0
fedilink
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 the comparison-addition model. This is the first result to break the $O(m+n\log n)$ time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.

Comments

alert-triangle
You must log in or register to comment.

Lobste.rs

lobsters

Subscribe from Remote Instance

You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !lobsters@lemmy.bestiver.se
lock
Community locked: only moderators can create posts. You can still comment on posts.

RSS Feed of lobste.rs

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 39 users / day
  • 130 users / week
  • 368 users / month
  • 1.24K users / 6 months
  • 2 local subscribers
  • 237 subscribers
  • 7.13K Posts
  • 351 Comments
  • Modlog
  • mods:
  • patrick
  • RSS Bot
  • BE: 0.19.5
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org