Vertex cover problem studied by cavity method: Analytics and population dynamics |
| |
Authors: | Haijun Zhou |
| |
Affiliation: | (1) Max-Planck-Institute of Colloids and Interfaces, 14424 Potsdam, Germany, DE |
| |
Abstract: | We study the vertex cover problem on finite connectivity random graphs by zero-temperature cavity method. The minimum vertex cover corresponds to the ground state(s) of a proposed Ising spin model. When the connectivity c > e = 2.718282, there is no state for this system as the reweighting parameter y, which takes a similar role as the inverse temperature β in conventional statistical physics, approaches infinity; consequently the ground state energy is obtained at a finite value of y when the free energy function attains its maximum value. The minimum vertex cover size at given c is estimated using population dynamics and compared with known rigorous bounds and numerical results. The backbone size is also calculated. Received 11 November 2002 Published online 1st April 2003 RID="a" ID="a"e-mail: zhou@mpikg-golm.mpg.de |
| |
Keywords: | PACS. 75.10.Nr Spin-glass and other random models – 89.75.-k Complex systems – 05.20.-y Classical statistical mechanics |
本文献已被 SpringerLink 等数据库收录! |