Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess
文献类型：期刊论文
| 作者 | Cai, Shaowei2; Lin, Jinkun1; Luo, Chuan3 |
| 刊名 | JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
 |
| 出版日期 | 2017 |
| 卷号 | 59页码:463-494 |
| ISSN号 | 1076-9757 |
| DOI | 10.1613/jair.5443 |
| 英文摘要 | 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. |
| 资助项目 | National Natural Science Foundation of China[61502464] ; 973 Program[2014CB340301] ; Youth Innovation Promotion Association, Chinese Academy of Sciences |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000411179900011 |
| 出版者 | AI ACCESS FOUNDATION |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/6834]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | Cai, Shaowei |
| 作者单位 | 1.Peking Univ, Sch Elect Engn & Comp Sci, Beijing, Peoples R China 2.Chinese Acad Sci, Inst Software, State Key Lab 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。