Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 116, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2019.104867
Keywords
Top-k clique search; Local search; Configuration checking; Clique scoring strategy
Categories
Funding
- National Natural Science Foundation of China [61976050, 61403076, 61802056, 61806050, 61806082]
- Fundamental Research Funds for the Central Universities [2412019E050]
- Liaoning Provincial Department of Education [LQN201912]
Ask authors/readers for more resources
The objective of the diversified top-k clique (DTKC) search problem is to find k maximal cliques that cover the maximum number of vertices in a given graph. This problem is equivalent to the well-known maximum clique problem (MaxClique) when k = 1. This paper proves the NP-hardness of the DTKC search problem and presents a local search algorithm, named TOPKLS, based on two novel strategies for the DTKC search problem. The first strategy is called enhanced configuration checking (ECC), which is a new variant of a recent effective strategy called configuration checking (CC), for reducing cycling in the local search and improving the diversity of the DTKC search problem. The second strategy is a heuristic to estimate the quality of each maximal clique. Experiments demonstrate that TOPKLS outperforms the existing algorithms on large sparse graphs from real-world applications. (C) 2019 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available