q-partitioning of graphs with finite coordination number

Publisher Website
Google Scholar
Abstract
The NP-complete optimisation problem of q-partitioning of graphs with finite connectivity is discussed. Using the effective local field method, the authors obtain the local field distributions with and without the continuous part and use them to calculate the ground-state energies of the three-state Potts spin glass on lattices with finite coordination number equal to three. This in turn gives analytic results for the optimal cost of the 3-partitioning of graphs. They perform simulations of actual 3-partitions of random graphs to compare with their theoretical results and obtain very good agreement. Ways for further improvement of the estimates are discussed.