"Any sufficiently sparse graph is indistinguishable from a linked list" comes to mind ;)
replyA linked list is sparse by the metric of minimum maximum degree (2).
replyA maximally sparse connected graph by mean (degree edge/node ratio) is any tree (mean degree ~ 1), not necessarily a linked list.
Yeah, just based on this article that really stood out. It seems to be for a different use-case than Djikstra’s. An average degree of 3.5 seems like an extremely practical a useful use-case in real life, I just don’t see any reason to put it and Djikstra’s against each-other in a head-to-head comparison.
reply