Empirical Evaluation of Graph Partitioning Using Spectral Embeddings and Flow


We present initial results from the first empirical evaluation of a graph partitioning algorithm inspired by the Arora-Rao-Vazirani algorithm, which combines spectral and flow methods in a novel way. We have studied the parameter space of this new algorithm, e.g., examining the extent to which different parameter settings interpolate between a more spectral and a more flow-based approach, and we have compared results of this algorithm to results from previously known and optimized algorithms such as METIS.

Proceedings of the International Symposium on Experimental Algorithms