Fast Solving Maximum Weight Clique Problem in Massive Graphs
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 568-573.
Abstract
This paper explores techniques for fast solving the maximum weight clique problem (MWCP) in very large scale real-world graphs. Because of the size of such graphs and the intractability of MWCP, previously developed algorithms may not be applicable. Although recent heuristic algorithms make progress in solving MWCP in massive graphs, they still need considerable time to get a good solution. In this work, we propose a new method for MWCP which interleaves between clique construction and graph reduction. We also propose three novel ideas to make it efficient, and develop an algorithm called FastWClq. Experiments on massive graphs from various applications show that, FastWClq finds better solutions than state of the art algorithms while the run time is much less. Further, FastWClq proves the optimal solution for about half of the graphs in an averaged time less than one second.
@inproceedings{ijcai2016p87,
title = {Fast Solving Maximum Weight Clique Problem in Massive Graphs},
author = {Cai, Shaowei and Lin, Jinkun},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {568--573},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/87},
}
TY - CPAPER TI - Fast Solving Maximum Weight Clique Problem in Massive Graphs AU - Cai, Shaowei AU - Lin, Jinkun T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 568 EP - 573 UR - https://ijcai.org/proceedings/2016/87 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
