An improved bit parallel exact maximum clique algorithm

An improved bit parallel exact maximum clique algorithm

0.00 Avg rating0 Votes
Article ID: iaor20132052
Volume: 7
Issue: 3
Start Page Number: 467
End Page Number: 479
Publication Date: Mar 2013
Journal: Optimization Letters
Authors: , , ,
Keywords: heuristics, graphs
Abstract:

This paper describes new improvements for BB‐MaxClique (San Segundo et al., 2011), a leading maximum clique algorithm which uses bit strings to efficiently compute basic operations during search by bit masking. Improvements include a recently described recoloring strategy in Tomita et al. (2010), which is now integrated in the bit string framework, as well as different optimization strategies for fast bit scanning. Reported results over DIMACS and random graphs show that the new variants improve over previous BB‐MaxClique for a vast majority of cases. It is also established that recoloring is mainly useful for graphs with high densities.

Reviews

Required fields are marked *. Your email address will not be published.