Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Graph Optimization Problems on a Bethe Lattice
Автор: Oliveira M.
The p-partitioning and p-coloring problems on a Bethe lattice of coordination number z are analyzed. It is shown that these two NP-complete optimization problems turn out to be equivalent to finding the ground-state energy of p-state Potts models with frustration. Numerical calculation of the cost function of both problems are carried out for several values of z and p. In the case of p = 2 the results are identical to those obtained by Mezard and Parisi for the case of the bipartitioning problem. A numerical upper bound to the chromatic number is found for several values of z.