Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess

doi:10.1613/jair.5443

	Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess
	Cai, Shaowei 1; Lin, Jinkun 2; Luo, Chuan 3
	2017
发表期刊	JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
ISSN	1076-9757
卷号	59 页码:463-494
摘要	The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NPhard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.
DOI	10.1613/jair.5443
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61502464] ; 973 Program[2014CB340301] ; Youth Innovation Promotion Association, Chinese Academy of Sciences
WOS研究方向	Computer Science
WOS类目	Computer Science, Artificial Intelligence
WOS记录号	WOS:000411179900011
出版者	AI ACCESS FOUNDATION
引用统计	被引频次：32[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/6835
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Cai, Shaowei
作者单位	1.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China 2.Peking Univ, Sch Elect Engn & Comp Sci, Beijing, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Cai, Shaowei,Lin, Jinkun,Luo, Chuan. Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess[J]. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH,2017,59:463-494.
APA	Cai, Shaowei,Lin, Jinkun,&Luo, Chuan.(2017).Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess.JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH,59,463-494.
MLA	Cai, Shaowei,et al."Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess".JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 59(2017):463-494.