A New Implicit Branching Strategy for Exact Maximum Clique
Pablo San Segundo, Cristóbal Tapia · 2010
We present a new implicit branching strategy for maximum clique. The new strategy is based in Konj and Janečič's improvement over reference MCR algorithm. It uses a fixed initial non increasing degree vertex ordering at every step of the search, to obtain tighter bounds than MCR on average. We show that the new branching strategy integrates nicely with a natural bit model for the domain. This allows for efficient bound computing using bit masking operations, so that overall improvement in performance is achieved. We present empirical validation over structured and random graphs.