Application of statistical mechanics to combinatorial optimization problems: The chromatic number problem and q-partitioning of a graph

Pik Yin Lai, Yadin Y. Goldschmidt

研究成果: 雜誌貢獻期刊論文同行評審

26 引文 斯高帕斯(Scopus)

摘要

Methods of statistical mechanics are applied to two important NP-complete combinatorial optimization problems. The first is the chromatic number problem, which seeks the minimal number of colors necessary to color a graph such that no two sites connected by an edge have the same color. The second is partitioning of a graph into q equal subgraphs so as to minimize intersubgraph connections. Both models are mapped into a frustrated Potts model, which is related to the q- state Potts spin glass. For the first problem, we obtain very good agreement with numerical simulations and theoretical bounds using the annealed approximation. The quenched model is also discussed. For the second problem we obtain analytic and numerical results by evaluating the groundstate energy of the q=3 and 4 Potts spin glass using Parisi's replica symmetry breaking. We also perform some numerical simulations to test the theoretical result and obtain very good agreement.

原文???core.languages.en_GB???
頁(從 - 到)513-529
頁數17
期刊Journal of Statistical Physics
48
發行號3-4
DOIs
出版狀態已出版 - 8月 1987

指紋

深入研究「Application of statistical mechanics to combinatorial optimization problems: The chromatic number problem and q-partitioning of a graph」主題。共同形成了獨特的指紋。

引用此