An exact bit-parallel algorithm for the maximum clique problem. (English) Zbl 1231.90369
Summary: 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.
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C15 | Coloring of graphs and hypergraphs |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Karp RM. In: Miller RE, Thatcher JW, editors. Reducibility among combinatorial problems. New York: Plenum; 1972. p. 85-103.; Karp RM. In: Miller RE, Thatcher JW, editors. Reducibility among combinatorial problems. New York: Plenum; 1972. p. 85-103. · Zbl 1467.68065 |
| [2] | Bahadur, D. K.C.; Akutsu, T.; Tomita, E.; Seki, T.; Fujijama, A., Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms, Genome Inform, 13, 143-152 (2002) |
| [3] | Butenko, S.; Wilhelm, W. E., Clique-detection models in computational biochemistry and genomics, Eur J Oper Res, 173, 1-17 (2006) · Zbl 1125.92025 |
| [4] | Hotta, K.; Tomita, E.; Takahashi, H., A view invariant human FACE detection method based on maximum cliques, Trans IPSJ, 44, SIG14 TOM9, 57-70 (2003) |
| [5] | San Segundo P, Rodríguez-Losada D, Matía F, Galán R. Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl Intell 2010;32(3):311-29; San Segundo P, Rodríguez-Losada D, Matía F, Galán R. Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl Intell 2010;32(3):311-29 |
| [6] | Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M., Hand book of combinatorial optimization, Supplement A (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, p. 1-74 · Zbl 1042.90002 |
| [7] | Heinz, E. A., How dark thought plays chess, ICCA J, 20, 3, 166-176 (1997) |
| [8] | Heinz, E. A., Scalable search in computer chess (2000), Vieweg |
| [9] | Baeza-Yates, R. A.; Gonnet, G. H., A new approach to text searching, Commun ACM, 35, 10, 74-82 (1992) |
| [10] | Tomita E, Seki T. An efficient branch and bound algorithm for finding a maximum clique. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V., editors. Discrete mathematics and theoretical computer science, Lecture Notes in Computer Science, vol. 2731, 2003. p. 278-89.; Tomita E, Seki T. An efficient branch and bound algorithm for finding a maximum clique. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V., editors. Discrete mathematics and theoretical computer science, Lecture Notes in Computer Science, vol. 2731, 2003. p. 278-89. · Zbl 1038.68565 |
| [11] | ÖOstergård, P. R.J., A fast algorithm for the maximum clique problem, Discrete Appl Math, 120, 1, 97-207 (2002) · Zbl 1019.05054 |
| [12] | Wood, D. R., An algorithm for finding a maximum clique in a graph, Oper Res Lett, 21, 211-217 (1977) · Zbl 0908.90264 |
| [13] | Carraghan, R.; Pardalos, P. M., An exact algorithm for the maximum clique problem, Oper Res Lett, 9, 375-382 (1990) · Zbl 0711.90080 |
| [14] | Konc, J.; Janečič, D., An improved branch and bound algorithm for the maximum clique problem, MATCH Commun Math Comput Chem, 58, 569-590 (2007) · Zbl 1274.05452 |
| [15] | (Johnson, D. S.; Trick, M. A., Cliques, coloring and satisfiability. DIMACS series in discrete mathematics and theoretical computer science 26 (1996), American Mathematical Society: American Mathematical Society Providence) |
| [16] | Warren, H. S., Hacker’s delight (2002), Addison-Wesley |
| [17] | Leiserson C, Prokop H, Randall K. Using de Bruijn sequences to index a 1 in a computer word. http://supertech.csail.mit.edu/papers/debruijn.pdf; Leiserson C, Prokop H, Randall K. Using de Bruijn sequences to index a 1 in a computer word. http://supertech.csail.mit.edu/papers/debruijn.pdf |
| [18] | Motzkin TS, Strauss EG. Maxima for graphs and a new proof of a theorem of Turan, 1965.; Motzkin TS, Strauss EG. Maxima for graphs and a new proof of a theorem of Turan, 1965. · Zbl 0129.39902 |
| [19] | Bomze, I. M., Evolution towards the maximum clique, J Global Optim, 10, 2, 143-164 (1997) · Zbl 0880.90110 |
| [20] | Fortin D, Tseveendorj I. Maximum clique regularizations (book chapter), Series of computers and operations research, vol.1. Optimization and optimal control (ISSN: 1793-7973). World Scientific; 2003.; Fortin D, Tseveendorj I. Maximum clique regularizations (book chapter), Series of computers and operations research, vol.1. Optimization and optimal control (ISSN: 1793-7973). World Scientific; 2003. |
| [21] | Gibbons, L. E.; Hearn, D. W.; Pardalos, P. M.; Ramana, M. V., Continuous characterizations of the maximum clique problem, Math Oper Res, 22, 3, 754-768 (1997) · Zbl 0883.90098 |
| [22] | Busygin, S., A new trust region technique for maximum weight clique, Discrete Appl Math, 154, 15, 2080-2096 (2006) · Zbl 1111.90020 |
| [23] | Bron, C.; Kerbosch, J., Finding all cliques of an undirected graph, Commun ACM, 16, 9, 575-577 (1971) · Zbl 0261.68018 |
| [24] | Biggs, N., Some heuristics for graph coloring, (Nelson, R.; Wilson, R. J., Graph colorings (1990), Longman: Longman New York), 87-96 · Zbl 0693.05031 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
