An efficient recursive decomposition algorithm for undirected graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911461475876864 |
|---|---|
| author | Heng, Pei Sun, Yi Guo, Jianhua |
| author_facet | Heng, Pei Sun, Yi Guo, Jianhua |
| contents | 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 closely aligns with the results of chordal graph decomposition. As a result, minimal triangulation of the graph is no longer required, and the identification of clique minimal separators is avoided. In the experimental section, we combine the proposed decomposition algorithm with two existing convex expansion methods. The results show that both combinations significantly outperform the existing algorithms in terms of efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19189 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An efficient recursive decomposition algorithm for undirected graphs Heng, Pei Sun, Yi Guo, Jianhua Data Structures and Algorithms Combinatorics 05C90 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 closely aligns with the results of chordal graph decomposition. As a result, minimal triangulation of the graph is no longer required, and the identification of clique minimal separators is avoided. In the experimental section, we combine the proposed decomposition algorithm with two existing convex expansion methods. The results show that both combinations significantly outperform the existing algorithms in terms of efficiency. |
| title | An efficient recursive decomposition algorithm for undirected graphs |
| topic | Data Structures and Algorithms Combinatorics 05C90 |
| url | https://arxiv.org/abs/2602.19189 |