An efficient local search algorithm for solving maximum edge weight clique problem in large graphs

doi:10.1007/s10878-020-00529-9

	An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
	Chu, Yi 1,2; Liu, Boxiao 1,2; Cai, Shaowei 3; Luo, Chuan 4,5; You, Haihang 1
	2020-02-04
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
页码	22
摘要	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.
关键词	Graph reduction Maximum edge weight clique problem Stochastic local search
DOI	10.1007/s10878-020-00529-9
收录类别	SCI
语种	英语
资助项目	National Key Research and Development Program of China[2017YFB0202502] ; Youth Innovation Promotion Association, Chinese Academy of Sciences[2017150]
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000511057700001
出版者	SPRINGER
引用统计	被引频次：5[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/14660
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	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.