StochColor: Stochastic Coloring based Graph Partitioning
Nishith Pathak, Arindam Banerjee, Jaideep Srivastava · University of Minnesota Digital Conservancy (University of Minnesota) · 2010
Graph partitioning is a classical problem in computer science. Most algorithms consist of heuristic, spectral and stochastic flow based methods. In this paper a novel technique for graph partitioning is presented. The proposed algorithm, called StochColor extracts partitions from the most likely state of a stochastic graph coloring process. Empirical results show that StochColor is comparable to or significantly better than state of the art spectral clustering and stochastic flow based methods, across a variety of applications.