StochColor: Stochastic Coloring based Graph Partitioning

Date of Submission: 
April 30, 2010
Report Number: 
10-011
Report PDF: 
Abstract: 
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.