Empirical Evaluation of Graph Partitioning Using Spectral Embeddings and Flow

Abstract

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.

Publication
Proceedings of the International Symposium on Experimental Algorithms

Related