Portal de Periódicos da CAPES

An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique

2003; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-45066-1_22

1611-3349

Etsuji Tomita, Tomokazu Seki,

Algorithms and Data Compression

We present an exact and efficient branch-and-bound algorithm for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular kind of graph. It employs approximate coloring and appropriate sorting of vertices to get an upper bound on the size of a maximum clique. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that our algorithm remarkably outperforms other existing algorithms in general. It has been successfully applied to interesting problems in bioinformatics, image processing, the design of quantum circuits, and the design of DNA and RNA sequences for bio-molecular computation.