Breaking the Sorting Barrier for Directed Single-Source Shortest Paths arxiv.org 95 points by pentestercrab 2 days ago
random3 2 days ago This was active a couple of days ago https://news.ycombinator.com/item?id=44812695
gsliepen 2 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. MarkusQ 2 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.
MarkusQ 2 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.
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.
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.