# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
An adaptive multistart tabu search approach to solve the maximum clique problem. (English) Zbl 1275.90084
Summary: Given an undirected graph $G=(V,E)$ with vertex set $V={1,\dots,n}$ and an edge set $E\subseteq V\times V$. The maximum clique problem is to determine in $G$ a clique (i.e. a complete subgraph) of maximum cardinality. This paper presents an effective algorithm for the maximum clique problem. The proposed multistart tabu search algorithm integrates a constrained neighborhood, a dynamic tabu tenure mechanism and a long term memory based restart strategy. Our proposed algorithm is evaluated on the whole set of 80 DIMACS challenge benchmarks and compared with five state-of-the-art algorithms. Computational results show that our proposed algorithm attains the largest known clique for 79 benchmarks.

##### MSC:
 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks 90C59 Approximation methods and heuristics
##### Software:
QUALEX; Tabu search; EXTRACOL; DIMACS
Full Text:
##### References:
 [1] Balas E, Yu CS (1986) Finding a maximum clique in an arbitrary graph. SIAM J Comput 15(4):1054--1068 · Zbl 0604.05024 · doi:10.1137/0215075 [2] Barbosa V, Campos L (2004) A novel evolutionary formulation of the maximum independent set problem. J Comb Optim 8(4):419--437 · Zbl 1079.90145 · doi:10.1007/s10878-004-4835-9 [3] Battiti R, Mascia F (2010) Reactive and dynamic local search for max-clique: engineering effective building blocks. Comput Oper Res 37(3):534--542 · Zbl 1173.90586 · doi:10.1016/j.cor.2009.02.013 [4] Battiti R, Protasi M (2001) Reactive local search for the maximum clique problem. Algorithmica 29(4):610--637 · Zbl 0985.68016 · doi:10.1007/s004530010074 [5] Bui T, Eppley P (1995) A hybrid genetic algorithm for the maximum clique problem. In: Proceedings of the 6th international conference on genetic algorithms, pp 478--484 [6] Busygin S, Butenko S, Pardalos PM (2002) A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere. J Comb Optim 6(3):287--297 · Zbl 1046.90071 · doi:10.1023/A:1014899909753 [7] Busygin S (2006) A new trust region technique for the maximum weight clique problem. Discrete Appl Math 154(1):2080--2096 · Zbl 1111.90020 · doi:10.1016/j.dam.2005.04.010 [8] Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9:375--382 · Zbl 0711.90080 · doi:10.1016/0167-6377(90)90057-C [9] Fleurent C, Ferland J (1996) Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. In: Johnson D, Trick M (eds) Proceedings of the 2nd DIMACS implementation challenge. DIMACS series in discrete mathematics and theoretical computer science, vol 26. Am. Math. Soc., Providence, pp 619--652 · Zbl 0864.90118 [10] Friden C, Hertz A, de Werra D (1989) Stabulus: A technique for finding stable sets in large graphs with tabu search. Computing 42:35--44 · Zbl 0685.68056 · doi:10.1007/BF02243141 [11] Galinier P, Hao JK (1999) Hybrid evolutionary algorithms for graph coloring. J Comb Optim 3(4):379--397 · Zbl 0958.90071 · doi:10.1023/A:1009823419804 [12] Gendreau M, Soriano P, Salvail L (1993) Solving the maximum clique problem using a tabu search approach. Ann Oper Res 41:385--403 · Zbl 0775.90297 · doi:10.1007/BF02023002 [13] Glover F, Laguna M (1997) Tabu search. Kluwer Academic, Norwell · Zbl 0930.90083 [14] Grosso A, Locatelli M, Pullan W (2008) Simple ingredients leading to very efficient heuristics for the maximum clique problem. J Heuristics 14(6):587--612 · Zbl 1173.90565 · doi:10.1007/s10732-007-9055-x [15] Johnson DS, Trick MA (1996) Second DIMACS implementation challenge: cliques, coloring and satisfiability. DIMACS series in discrete mathe-matics and theoretical computer science, vol 26. Am. Math. Soc., Providence [16] Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85--103 [17] Katayama K, Hamamoto A, Narihisa H (2005) An effective local search for the maximum clique problem. Inf Process Lett 95(5):503--511 · Zbl 1185.68283 · doi:10.1016/j.ipl.2005.05.010 [18] Marchiori E (1998) A simple heuristic based genetic algorithm for the maximum clique problem. In: Proceedings of ACM symposium on applied computing, pp 366--373 [19] Marchiori E (2002) Genetic, iterated and multistart local search for the maximum clique problem. In: Applications of evolutionary computing. Proceedings of EvoWorkshops, vol 2279, pp 112--121 · Zbl 1044.68780 [20] Östergärd PJR (2002) A fast algorithm for the maximum clique problem. Discrete Appl Math 120:195--205 [21] Pardalos PM, Xue J (2002) The maximum clique problem. J Glob Optim 4:301--328 · Zbl 0797.90108 · doi:10.1007/BF01098364 [22] Pullan W (2006) Phased local search for the maximum clique problem. J Comb Optim 12(3):303--323 · Zbl 1255.90122 · doi:10.1007/s10878-006-9635-y [23] Pullan W, Hoos HH (2006) Dynamic local search for the maximum clique problem. J Artif Intell Res 25:159--185 · Zbl 1182.68065 [24] Rebennack S, Oswald M, Theis DO, Seitz H, Reinelt G, Pardalos PM (2011) A Branch and Cut solver for the maximum stable set problem. J Comb Optim 21(4):434--457 · Zbl 1319.90079 · doi:10.1007/s10878-009-9264-3 [25] Singh A, Gupta AK (2008) A hybrid heuristic for the maximum clique problem. J Heuristics 12:5--22 · Zbl 1122.90070 · doi:10.1007/s10732-006-3750-x [26] Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. Discrete Math Theor Comput Sci 2731:278--289 · Zbl 1038.68565 · doi:10.1007/3-540-45066-1_22 [27] Zhang QF, Sun JY, Tsang E (2005) Evolutionary algorithm with the guided mutation for the maximum clique problem. IEEE Trans Evol Comput 9(2):192--200 · doi:10.1109/TEVC.2004.840835 [28] Wu Q, Hao JK (2012a) Coloring large graphs based on independent set extraction. Comput Oper Res 39(2):283--290 · Zbl 1250.05007 · doi:10.1016/j.cor.2011.04.002 [29] Wu Q, Hao JK (2012b) An effective heuristic algorithm for sum coloring of graphs. Comput. Oper. Res. 39(7):1593--1600. doi: 10.1016/j.cor.2011.09.010 · Zbl 1250.05114 · doi:10.1016/j.cor.2011.09.010