top | item 47004375 (no title) usrusr | 16 days ago "Any sufficiently sparse graph is indistinguishable from a linked list" comes to mind ;) discuss order hn newest gowld|16 days ago A 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.
gowld|16 days ago A 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.
gowld|16 days ago
A maximally sparse connected graph by mean (degree edge/node ratio) is any tree (mean degree ~ 1), not necessarily a linked list.