Spectral partitioning of graphs into compact, connected regions
By: Ewan Davies , Ryan Job , Maxine Kampbell and more
Potential Business Impact:
Divides a map into connected, balanced pieces.
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.
Similar Papers
Reweighted Spectral Partitioning Works: Bounds for Special Graph Classes
Data Structures and Algorithms
Finds better ways to split computer networks.
Reweighted Spectral Partitioning Works: Bounds for Special Graph Classes
Data Structures and Algorithms
Finds better ways to cut networks apart.
An Improved and Generalised Analysis for Spectral Clustering
Machine Learning (CS)
Finds hidden groups in connected information.