Wikipedia:Reference desk/Archives/Mathematics/2023 April 23

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 23

Sorting graph by n-connected components for increasing n

Is there a term for an ordering of a graph's nodes that is first by connected component, then within each connected component into biconnected component, then within each biconnected component into triconnected components and so on? Also, is it possible to generate such an ordering in polynomial time? My use case for this is to order a DAG of tasks with overlapping subtasks so that every subtask result is cached in memory and reused by every task that needs it, but there isn't enough memory to cache all reused subtask results at once, and I'm trying to avoid the quadratic overhead of a naive online algorithm. NeonMerlin 04:52, 23 April 2023 (UTC)

I took the liberty of moving the link to Connectivity (graph theory), instead of the topological concept. --RDBury (talk) 06:20, 23 April 2023 (UTC)

We also have an article Component (graph theory).  --Lambiam 10:05, 23 April 2023 (UTC)