nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.07.2013

An adaptive multistart tabu search approach to solve the maximum clique problem

verfasst von: Qinghua Wu, Jin-Kao Hao

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Given an undirected graph G=(V,E) with vertex set V={1,…,n} and edge set E⊆V×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.

Vorheriger Artikel On the union of intermediate nodes of shortest paths

Nächster Artikel The maximum flow problem with disjunctive constraints

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The source code of AMTS is available at: http://www.info.univ-angers.fr/pub/hao/amts.html.

Balas E, Yu CS (1986) Finding a maximum clique in an arbitrary graph. SIAM J Comput 15(4):1054–1068 MathSciNetMATHCrossRef

Barbosa V, Campos L (2004) A novel evolutionary formulation of the maximum independent set problem. J Comb Optim 8(4):419–437 MathSciNetMATHCrossRef

Battiti R, Mascia F (2010) Reactive and dynamic local search for max-clique: engineering effective building blocks. Comput Oper Res 37(3):534–542 MathSciNetMATHCrossRef

Battiti R, Protasi M (2001) Reactive local search for the maximum clique problem. Algorithmica 29(4):610–637 MathSciNetMATHCrossRef

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

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 MathSciNetMATHCrossRef

Busygin S (2006) A new trust region technique for the maximum weight clique problem. Discrete Appl Math 154(1):2080–2096 MathSciNetMATHCrossRef

Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9:375–382 MATHCrossRef

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

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 MATHCrossRef

Galinier P, Hao JK (1999) Hybrid evolutionary algorithms for graph coloring. J Comb Optim 3(4):379–397 MathSciNetMATHCrossRef

Gendreau M, Soriano P, Salvail L (1993) Solving the maximum clique problem using a tabu search approach. Ann Oper Res 41:385–403 MATHCrossRef

Glover F, Laguna M (1997) Tabu search. Kluwer Academic, Norwell MATHCrossRef

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 CrossRef

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 MATH

Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85–103 CrossRef

Katayama K, Hamamoto A, Narihisa H (2005) An effective local search for the maximum clique problem. Inf Process Lett 95(5):503–511 MathSciNetMATHCrossRef

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

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 CrossRef

Östergärd PJR (2002) A fast algorithm for the maximum clique problem. Discrete Appl Math 120:195–205 CrossRef

Pardalos PM, Xue J (2002) The maximum clique problem. J Glob Optim 4:301–328 MathSciNetCrossRef

Pullan W (2006) Phased local search for the maximum clique problem. J Comb Optim 12(3):303–323 MathSciNetMATHCrossRef

Pullan W, Hoos HH (2006) Dynamic local search for the maximum clique problem. J Artif Intell Res 25:159–185 MATH

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 MathSciNetCrossRef

Singh A, Gupta AK (2008) A hybrid heuristic for the maximum clique problem. J Heuristics 12:5–22 CrossRef

Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. Discrete Math Theor Comput Sci 2731:278–289 MathSciNetCrossRef

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 CrossRef

Wu Q, Hao JK (2012a) Coloring large graphs based on independent set extraction. Comput Oper Res 39(2):283–290 MathSciNetMATHCrossRef

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 MathSciNetMATHCrossRef

Titel: An adaptive multistart tabu search approach to solve the maximum clique problem
verfasst von: Qinghua Wu
Jin-Kao Hao
Publikationsdatum: 01.07.2013
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2013
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-011-9437-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2013

On the union of intermediate nodes of shortest paths

Practical unicast and convergecast scheduling schemes for cognitive radio networks

Parameterized complexity of k-anonymity: hardness and tractability

Independent dominating sets in regular graphs

On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines

On the outer-connected domination in graphs

Premium Partner