An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
文献类型：期刊论文
| 作者 | Chu, Yi1,2; Liu, Boxiao1,2; Cai, Shaowei3; Luo, Chuan4,5; You, Haihang1 |
| 刊名 | JOURNAL OF COMBINATORIAL OPTIMIZATION
 |
| 出版日期 | 2020-02-04 |
| 页码 | 22 |
| 关键词 | Graph reduction Maximum edge weight clique problem Stochastic local search |
| ISSN号 | 1382-6905 |
| DOI | 10.1007/s10878-020-00529-9 |
| 英文摘要 | Maximum vertex weight clique problem (MVWCP) and maximum edge weight clique problem (MEWCP) are two significant generalizations of maximum clique problem (MCP), and can be widely used in many real-world applications including molecular biology, broadband network design and pattern recognition. Recently, breakthroughs have been made for solving MVWCP in large graphs, resulting in several state-of-the-art algorithms, such as WLMC, FastWClq and LSCC + BMS. However, less attention has been paid to solving MEWCP in large graphs. In this paper, we present an efficient Stochastic Local Search (SLS) algorithm for MEWCP by combining clique construction, local search and graph reduction, resulting in a new algorithm named ReConSLS. We also propose a new upper bound function for edge weighted graphs which is essential for graph reduction. Extensive experiments on a wide range of large graphs demonstrate that ReConSLS surpasses state-of-the-art SLS competitors on the majority of testing graphs. |
| 资助项目 | National Key Research and Development Program of China[2017YFB0202502] ; Youth Innovation Promotion Association, Chinese Academy of Sciences[2017150] |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000511057700001 |
| 出版者 | SPRINGER |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/14659]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | You, Haihang |
| 作者单位 | 1.Chinese Acad Sci, State Key Lab Comp Architecture, Inst Comp Technol, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 3.Chinese Acad Sci, State Key Lab Comp Sci, Inst Software, Beijing 100190, Peoples R China 4.Leiden Univ, Leiden Inst Adv Comp Sci, Leiden, Netherlands 5.Microsoft Res, Beijing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Chu, Yi,Liu, Boxiao,Cai, Shaowei,et al. An efficient local search algorithm for solving maximum edge weight clique problem in large graphs[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2020:22. |
| APA | Chu, Yi,Liu, Boxiao,Cai, Shaowei,Luo, Chuan,&You, Haihang.(2020).An efficient local search algorithm for solving maximum edge weight clique problem in large graphs.JOURNAL OF COMBINATORIAL OPTIMIZATION,22. |
| MLA | Chu, Yi,et al."An efficient local search algorithm for solving maximum edge weight clique problem in large graphs".JOURNAL OF COMBINATORIAL OPTIMIZATION (2020):22. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。