QQ客服 官方微博 反馈留言

	Two new local search strategies for minimum vertex cover
	Cai, Shaowei ; Su, Kaile ; Sattar, Abdul
	2012
英文摘要	In this paper, we propose two new strategies to design efficient local search algorithms for the minimum vertex cover (MVC) problem. There are two main drawbacks in state-of-the-art MVC local search algorithms: First, they select a pair of vertices to be exchanged simultaneously, which is time consuming; Second, although they use edge weighting techniques, they do not have a strategy to decrease the weights. To address these drawbacks, we propose two new strategies: two stage exchange and edge weighting with forgetting. The two stage exchange strategy selects two vertices to be exchanged separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. We utilize these two strategies to design a new algorithm dubbed NuMVC. The experimental results show that NuMVC significantly outperforms existing state-of-the-art heuristic algorithms on most of the hard DIMACS instances and all instances in the hard random BHOSLIB benchmark. Copyright ? 2012, Association for the Advancement of Artificial Intelligence. All rights reserved.; EI; 0
语种	英语
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/412184]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Cai, Shaowei,Su, Kaile,Sattar, Abdul. Two new local search strategies for minimum vertex cover. 2012-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。