Hacker News new | ask | show | jobs
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (arxiv.org)
99 points by pentestercrab 311 days ago
2 comments
random3 311 days ago
This was active a couple of days ago https://news.ycombinator.com/item?id=44812695
link
gsliepen 311 days ago
At first glance it looks like this is very useful, but it only gives a speedup for very sparse graphs with an average degree of less than 3, unless your graph is very big, as in trillions of vertices.
link
MarkusQ 311 days ago
Degree less than 6? If m < 3n that means there are three times as many edges as nodes, and each edge connect to two vertices.

So 2d square latices would still benefit.

But yeah, not a total domination.

link