Q-partitioning of graphs with finite coordination number

Y. Y. Goldschmidt, P. -Y.lai

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

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.

Original languageEnglish
Article number001
Pages (from-to)L1043-L1049
JournalJournal of Physics A: General Physics
Volume21
Issue number22
DOIs
StatePublished - 1988

Fingerprint

Dive into the research topics of 'Q-partitioning of graphs with finite coordination number'. Together they form a unique fingerprint.

Cite this