کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474974 | 699189 | 2016 | 14 صفحه PDF | دانلود رایگان |
• New state-of-the-art exact maximum bit-parallel clique algorithm tailored for massive graphs.
• New sparse bit parallel encoding.
• Improved preprocessing to reduce the problem´s scale.
This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields.State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds.Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds.
Journal: Computers & Operations Research - Volume 66, February 2016, Pages 81–94