Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (opens in new tab)

(arxiv.org)

99 pointspentestercrab7mo ago3 comments

3 comments

This was active a couple of days ago https://news.ycombinator.com/item?id=44812695

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.

MarkusQ7mo 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.

j / k navigate · click thread line to collapse