An efficient recursive decomposition algorithm for undirected graphs
The decomposition of undirected graphs simplifies complex problems by breaking them into solvable subgraphs, following the philosophy of divide and conquer. This paper investigates the relationship between atom decomposition and the maximum cardinality search (MCS) ordering in general undirected graphs. Specifically, we prove that applying a convex extension to the node numbered $1$ and its neighborhood in an MCS ordering yields an atom in the graph. Furthermore, based on the MCS ordering, we introduce a recursive algorithm for decomposing an undirected graph into its atoms. This approach…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.19189
curl -X POST /api/v1/records/arxiv/2602.19189/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.19189/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'