Clustering Analysis of Minimum Vertex-cover Problem Using Inter-frustration

摘要：

In this paper,we investigated a novel interfrustration structure in the solution space of spin glass models and employed this novel structure to study the clustering phenomenon of the minimum vertex cover problem.Our results show-that the long range inter-frustration,which emerges when the average degree c > e.can provide 1) a detailed description of the clustering structure,2) how replica symmetry breaking occurs.Moreover,this long range interfrustration persists under one-step replica symmetric breaking (starting about c =10),which means it could be used for investigating high order replica symmetric breaking.We also analyzed the algorithmic complexity caused by the long range inter-frustration structure.

作者: Binghui Guo Yang Zhang Hongbo Zhou Zhiming Zheng

作者单位: LMIB and School of Mathematics and Systems Science Beihang University Beijing,China Computer Science Department Southern Illinois University Carbondale IL,USA

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer and Network Technology(ICCNT 2011)(2011第三届IEEE计算机与网络技术国际会议)

会议地点: 太原

会议语种:英文

页码: 580-583

在线出版日期: 2011-02-26（万方平台首次上网日期，不代表论文的发表时间）