At first glance it looks like this is very useful, but it only gives a speedup f... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		gsliepen 41 days ago \| parent \| context \| favorite \| on: Breaking the Sorting Barrier for Directed Single-S... 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 41 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.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact