首 页机构概况机构设置科研人才队伍合作交流研究生教育博士后图书馆创新文化党群园地院重点实验室彭桓武中心信息公开
  学术活动
  您现在的位置:首页 > 学术活动 > 专题学术报告/Seminar
Detecting the Solution Space of Vertex-Cover by Interactions and Backbones
2012-01-06  【 】【打印】【关闭
Institute of Theoretical Physics
Chinese Academy of Sciences
学术报告
Title
题目
Detecting the Solution Space of Vertex-Cover by Interactions and Backbones
Speaker
报告人
韦卫博士,张仁权博士
北京航空航天大学数学与系统科学学院
Date
日期
2012-01-06 AM 10:00 Friday
Venue
地点
Conference Hall 322, ITP/理论物理所322报告厅
Abstract
摘要

To solve the combinatorial optimization problems especially the minimal Vertex-cover problem with high efficiency, is a significant task in theoretical computer science and many other subjects. Aiming at detecting the solution space of Vertex-cover, a new structure named interaction between nodes is defined and discovered for random graph, which results in the emergence of the frustration and long-range correlation phenomenon. Based on the backbones and interactions with a node adding process, we propose an Interaction and Backbone Evolution Algorithm to achieve the reduced solution graph, which has a direct correspondence to the solution space of Vertex-cover. By this algorithm, the whole solution space can be obtained strictly when there is no leaf-removal core on the graph and the odd cycles of unfrozen nodes bring great obstacles to its efficiency. Besides, this algorithm possesses favorable exactness and has good performance on random instances even with high average degrees. The interaction with the algorithm provides a new viewpoint to solve Vertex-cover, which will have a wide range of applications to different types of graphs, better usage of which can lower the computational complexity for solving Vertex-cover.

IE6.0浏览器,1024X768分辨率 版权所有 ? 中国科学院理论物理研究所
地址:北京市海淀区中关村东路55号 邮政编码:100190
京ICP备05002865号】 京公网安备1101080094号