3 ms·
"Any sufficiently sparse graph is indistinguishable from a linked list" comes to mind ;)
by usrusr 8mo ago
"Any sufficiently sparse graph is indistinguishable from a linked list" comes to mind ;)
- gowld 8mo agoA linked list is sparse by the metric of minimum maximum degree (2). A maximally sparse connected graph by mean (degree edge/node ratio) is any tree (mean degree ~ 1), not necessarily a linked list.