An exact bit-parallel algorithm for the maximum clique problem |
| |
Authors: | Pablo San Segundo,Diego Rodrí guez-LosadaAgustí n Jimé nez |
| |
Affiliation: | Intelligent Control Group, Universidad Politécnica de Madrid (CAR-UPM), C/ Jose Gutiérrez Abascal, 2, 28006 Madrid, Spain |
| |
Abstract: | This paper presents a new exact maximum clique algorithm which improves the bounds obtained in state of the art approximate coloring by reordering the vertices at each step. Moreover, the algorithm can make full use of bit strings to sort vertices in constant time as well as to compute graph transitions and bounds efficiently, exploiting the ability of CPUs to process bitwise operations in blocks of size the ALU register word. As a result it significantly outperforms a current leading algorithm. |
| |
Keywords: | Maximum clique Bit string Branch and bound Coloring Bit-parallelism |
本文献已被 ScienceDirect 等数据库收录! |