Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.13982 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909650358632448 |
|---|---|
| author | Davies, Ewan Job, Ryan Kampbell, Maxine Kim, Hannah Seo, Hyojin |
| author_facet | Davies, Ewan Job, Ryan Kampbell, Maxine Kim, Hannah Seo, Hyojin |
| contents | We define and study a spectral recombination algorithm, SpecReCom, for partitioning a graph into a given number of connected parts. It is straightforward to introduce additional constraints such as the requirement that the weight (or number of vertices) in each part is approximately balanced, and we exemplify this by stating a variant, BalSpecReCom, of the SpecReCom algorithm. We provide empirical evidence that the algorithm achieves more compact partitions than alternatives such as RevReCom by studying a $56\times 56$ grid graph and a planar graph obtained from the state of Colorado. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_13982 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectral partitioning of graphs into compact, connected regions Davies, Ewan Job, Ryan Kampbell, Maxine Kim, Hannah Seo, Hyojin Data Structures and Algorithms Physics and Society We define and study a spectral recombination algorithm, SpecReCom, for partitioning a graph into a given number of connected parts. It is straightforward to introduce additional constraints such as the requirement that the weight (or number of vertices) in each part is approximately balanced, and we exemplify this by stating a variant, BalSpecReCom, of the SpecReCom algorithm. We provide empirical evidence that the algorithm achieves more compact partitions than alternatives such as RevReCom by studying a $56\times 56$ grid graph and a planar graph obtained from the state of Colorado. |
| title | Spectral partitioning of graphs into compact, connected regions |
| topic | Data Structures and Algorithms Physics and Society |
| url | https://arxiv.org/abs/2506.13982 |