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

(arxiv.org)

99 pointspentestercrab10mo ago3 comments

3 comments

3 comments · 2 top-level

gsliepen10mo ago· 1 in thread

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.

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

random310mo ago

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

j / k navigate · click thread line to collapse