Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
(
arxiv.org
)
99 points
by
pentestercrab
7 months ago
|
hide
|
past
|
favorite
|
3 comments
random3
7 months ago
|
next
[–]
This was active a couple of days ago
https://news.ycombinator.com/item?id=44812695
gsliepen
7 months ago
|
prev
[–]
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
7 months ago
|
parent
[–]
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.
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search: