{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T11:58:11Z","timestamp":1768737491130,"version":"3.49.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,12,1]],"date-time":"1993-12-01T00:00:00Z","timestamp":754704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1993,12]]},"DOI":"10.1007\/bf02023002","type":"journal-article","created":{"date-parts":[[2005,8,10]],"date-time":"2005-08-10T13:49:15Z","timestamp":1123681755000},"page":"385-403","source":"Crossref","is-referenced-by-count":83,"title":["Solving the maximum clique problem using a tabu search approach"],"prefix":"10.1007","volume":"41","author":[{"given":"Michel","family":"Gendreau","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Soriano","sequence":"additional","affiliation":[]},{"given":"Louis","family":"Salvail","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02023002_CR1","volume-title":"Economic Applications of the Theory of Graphs","author":"G. Avondo-Bodeno","year":"1962","unstructured":"G. Avondo-Bodeno,Economic Applications of the Theory of Graphs (Gordon and Breach, New York, 1962)."},{"key":"BF02023002_CR2","unstructured":"L. Babel, Finding maximum cliques in arbitrary and in special graphs, Report TUM-M9008, Mathematisches Institut und Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen (1990), to appear in Computing."},{"key":"BF02023002_CR3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF01415983","volume":"34","author":"L. Babel","year":"1990","unstructured":"L. Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem, Zeits. Oper. Res. 34(1990)207\u2013217.","journal-title":"Zeits. Oper. Res."},{"key":"BF02023002_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1137\/0220012","volume":"20","author":"E. Balas","year":"1991","unstructured":"E. Balas and J. Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM J. Comput. 20(1991)209\u2013221.","journal-title":"SIAM J. Comput."},{"key":"BF02023002_CR5","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1137\/0215075","volume":"15","author":"E. Balas","year":"1986","unstructured":"E. Balas and C.S Yu, Finding a maximum clique in an arbitrary graph, SIAM J. Comput. 15(1986)1054\u20131068.","journal-title":"SIAM J. Comput."},{"key":"BF02023002_CR6","volume-title":"Th\u00e9orie des Graphes et ses Applications","author":"C. Berge","year":"1962","unstructured":"C. Berge,Th\u00e9orie des Graphes et ses Applications (Dunod, Paris, 1962)."},{"key":"BF02023002_CR7","volume-title":"Random Graphs","author":"B. Bollobas","year":"1985","unstructured":"B. Bollobas,Random Graphs (Academic Press, London, 1985)."},{"key":"BF02023002_CR8","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1017\/S0305004100053056","volume":"80","author":"B. Bollobas","year":"1976","unstructured":"B. Bollobas and P. Erd\u00f6s, Cliques in random graphs, Math. Proc. Camb. Phil. Soc. 80(1976)419\u2013427.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"BF02023002_CR9","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C. Bron","year":"1973","unstructured":"C. Bron and J. Kerbosch, Finding all cliques of an undirected graph, Comm. ACM 16(1973)575\u2013577.","journal-title":"Comm. ACM"},{"key":"BF02023002_CR10","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R. Carraghan","year":"1990","unstructured":"R. Carraghan and P.M. Pardalos, An exact algorithm for the maximum clique problem, Oper. Res. Lett. 9(1990)375\u2013382.","journal-title":"Oper. Res. Lett."},{"key":"BF02023002_CR11","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1051\/ro\/197509V100051","volume":"9","author":"V. Degot","year":"1975","unstructured":"V. Degot and J.M. Hualde, De l'utilisation de la notion de clique (sous-graphe complet sym\u00e9trique) en mati\u00e8re de typologie des populations, Revue fran\u00e7aise d'automatique et recherche op\u00e9rationelle: Recherche op\u00e9rationelle 9(1975)5\u201318.","journal-title":"Revue fran\u00e7aise d'automatique et recherche op\u00e9rationelle: Recherche op\u00e9rationelle"},{"key":"BF02023002_CR12","volume-title":"Graph Theory with Applications to Engineering and Computer Science","author":"N. Deo","year":"1974","unstructured":"N. Deo,Graph Theory with Applications to Engineering and Computer Science (Prentice-Hall, Englewood Cliffs, 1974)."},{"key":"BF02023002_CR13","first-page":"83","volume":"19","author":"C. Ebenegger","year":"1984","unstructured":"C. Ebenegger, P.L. Hammer and D. de Werra, Pseudo-Boolean functions and stability of graphs, Ann. Discr. Math. 19(1984)83\u201398.","journal-title":"Ann. Discr. Math."},{"key":"BF02023002_CR14","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02243141","volume":"42","author":"C. Friden","year":"1989","unstructured":"C. Friden, A Hertz and D. de Werra, Stabulus: a technique for finding stable sets in large graphs with tabu search, Computing 42(1989)35\u201344.","journal-title":"Computing"},{"key":"BF02023002_CR15","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/0305-0548(90)90048-C","volume":"17","author":"C. Friden","year":"1990","unstructured":"C. Friden, A Hertz and D. de Werra, Tabaris: An exact algorithm based on tabu search for finding a maximum independent set in a graph, Comput. Oper. Res. 17(1990)437\u2013445.","journal-title":"Comput. Oper. Res."},{"key":"BF02023002_CR16","volume-title":"Computers and Intractibility: a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson,Computers and Intractibility: a Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979)."},{"key":"BF02023002_CR17","unstructured":"M. Gendreau, A fast greedy algorithm for the maximum clique problem, paper presented at the TIMS\/ORSA Meeting, New Orleans (May 1987)."},{"key":"BF02023002_CR18","volume-title":"Advances in Optimization and Control","author":"M. Gendreau","year":"1988","unstructured":"M. Gendreau, J.-C. Picard and L. Zubieta, An efficient implicit enumeration algorithm for the maximum clique problem, in:Advances in Optimization and Control ed. H.A. Eiselt and G. Pederzoli (Springer, Berlin, 1988)."},{"key":"BF02023002_CR19","unstructured":"M. Gendreau, L. Salvail and P. Soriano, An appraisal of greedy heuristics for the maximum clique problem, Centre de Recherche sur les Transports, Universit\u00e9 de Montr\u00e9al, forthcoming."},{"key":"BF02023002_CR20","unstructured":"M. Gendreau, P. Soriano and L. Salvail, Simulated annealing and cliques, Centre de Recherche sur les Transports, Universit\u00e9 de Montr\u00e9al, forthcoming; paper presented at the ORSA\/TIMS Meeting, New York (October 1989)."},{"key":"BF02023002_CR21","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF02248731","volume":"21","author":"L. Gerhards","year":"1979","unstructured":"L. Gerhards and W. Lindenberg, Clique detection for nondirected graphs: two new algorithms, Computing 21 (1979)295\u2013322.","journal-title":"Computing"},{"key":"BF02023002_CR22","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F. Glover","year":"1986","unstructured":"F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res. 13(1986)533\u2013549.","journal-title":"Comput. Oper. Res."},{"key":"BF02023002_CR23","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F. Glover","year":"1989","unstructured":"F. Glover, Tabu search. Part I, ORSA J. Comput. 1(1989)190\u2013206.","journal-title":"ORSA J. Comput."},{"key":"BF02023002_CR24","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/ijoc.2.1.4","volume":"2","author":"F. Glover","year":"1990","unstructured":"F. Glover, Tabu search. Part II, ORSA J. Comput. 2(1990)4\u201332.","journal-title":"ORSA J. Comput."},{"key":"BF02023002_CR25","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1109\/TCAD.1986.1270190","volume":"CAD-5","author":"J.W. Greene","year":"1986","unstructured":"J.W. Greene and K.J. Supowit, Simulated annealing without rejected moves, IEEE Trans. Comput. Aided Des. CAD-5(1986)221\u2013228.","journal-title":"IEEE Trans. Comput. Aided Des."},{"key":"BF02023002_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lovasz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988)."},{"key":"BF02023002_CR27","unstructured":"P. Hansen and B. Jaumard, Algorithms for the maximum satisfiability problem, RUTCOR Research Report 43\u201387, Rutgers University (1987)."},{"key":"BF02023002_CR28","volume-title":"Graph Theory and its Applications","author":"F. Harary","year":"1970","unstructured":"F. Harary, Graph theory as a structural model in the social sciences, in:Graph Theory and its Applications, ed. B. Harris (Academic Press, New York, 1970)."},{"key":"BF02023002_CR29","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF02239976","volume":"29","author":"A. Hertz","year":"1987","unstructured":"A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 29(1987)345\u2013351.","journal-title":"Computing"},{"key":"BF02023002_CR30","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci. 9(1974)256\u2013278.","journal-title":"J. Comput. Syst. Sci."},{"key":"BF02023002_CR31","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"D.S. Johnson, M. Yannakakis and C.H. Papadimitriou, On generating all maximal independent sets, Inf. Proc. Lett. 27(1988)119\u2013123.","journal-title":"Inf. Proc. Lett."},{"key":"BF02023002_CR32","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983)671\u2013680.","journal-title":"Science"},{"key":"BF02023002_CR33","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/0898-1221(83)90115-3","volume":"9","author":"E. Loukakis","year":"1983","unstructured":"E. Loukakis, A new backtracking algorithm for generating the family of maximal independent sets of a graph, Comput. Math. Appl. 9(1983)583\u2013589.","journal-title":"Comput. Math. Appl."},{"key":"BF02023002_CR34","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1080\/00207168208803311","volume":"11","author":"E. Loukakis","year":"1982","unstructured":"E. Loukakis and C. Tsouros, Determining the number of internal stability of a graph, Int. J. Comput. Math. 11(1982)207\u2013220.","journal-title":"Int. J. Comput. Math."},{"key":"BF02023002_CR35","unstructured":"D.W. Matula, The employee party problem, Not. A.M.S. 19(1972)A-382."},{"key":"BF02023002_CR36","unstructured":"D.W. Matula, The largest clique in a random graph, Technical Report CS7608, Southern Methodist University (1976)."},{"key":"BF02023002_CR37","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02579304","volume":"7","author":"D.W. Matula","year":"1987","unstructured":"D.W. Matula, Expose-and-merge exploration and the chromatic number of a random graph, Combinatorica 7(1987)275\u2013284.","journal-title":"Combinatorica"},{"key":"BF02023002_CR38","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/00207169108803967","volume":"38","author":"P.M. Pardalos","year":"1991","unstructured":"P.M. Pardalos and N. Desai, An algorithm for finding a maximum weighted independent set in arbitrary graph, Int. J. Comput. Math. 38(1991)163\u2013175.","journal-title":"Int. J. Comput. Math."},{"key":"BF02023002_CR39","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1080\/00207169008803851","volume":"33","author":"P.M. Pardalos","year":"1990","unstructured":"P.M. Pardalos and A. Phillips, A global optimization approach for solving the maximum clique problem, Int. J. Comput. Math. 33((1990)209\u2013216.","journal-title":"Int. J. Comput. Math."},{"key":"BF02023002_CR40","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0305-0548(92)90067-F","volume":"19","author":"P.M. Pardalos","year":"1992","unstructured":"P.M. Pardalos and G.P. Rodgers, A branch and bound algorithm for the maximum clique problem, Comp. Oper. Res. 19(1992)363\u2013375.","journal-title":"Comp. Oper. Res."},{"key":"BF02023002_CR41","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"J.M. Robson, Algorithms for the maximum independent sets, J. Algor. 7(1986)425\u2013440.","journal-title":"J. Algor."},{"key":"BF02023002_CR42","volume-title":"Alg\u00e8bre Moderne et Th\u00e9orie des Graphes, Vol. 1","author":"B. Roy","year":"1969","unstructured":"B. Roy,Alg\u00e8bre Moderne et Th\u00e9orie des Graphes, Vol. 1 (Dunod, Paris, 1969)."},{"key":"BF02023002_CR43","doi-asserted-by":"crossref","unstructured":"C.E. Shannon, The zero-error capacity of a noisy channel,Symp. on Information Theory, I.R.E. Trans. 3(1956).","DOI":"10.1109\/TIT.1956.1056798"},{"key":"BF02023002_CR44","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"R.E. Tarjan and A.E. Trojanowski, Finding a maximum independent set, SIAM J. Comput. 6(1977)537\u2013546.","journal-title":"SIAM J. Comput."},{"key":"BF02023002_CR45","doi-asserted-by":"crossref","unstructured":"J. Turner and W.H. Kautz, A survey of progress in graph theory in the Soviet Union, SIAM 12(1970).","DOI":"10.1137\/1012125"},{"key":"BF02023002_CR46","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF01720782","volume":"11","author":"D. Werra de","year":"1989","unstructured":"D. de Werra and A. Hertz, Tabu search techniques: A tutorial and application to neural networks, OR Spektrum 11(1989)131\u2013141.","journal-title":"OR Spektrum"},{"key":"BF02023002_CR47","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/0377-2217(89)90383-4","volume":"41","author":"M. Widmer","year":"1989","unstructured":"M. Widmer and A. Hertz, A new heuristic method for solving the flow shop sequencing problem, Eur. J. Oper. Res. 41(1989)186\u2013193.","journal-title":"Eur. J. Oper. Res."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02023002.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02023002\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02023002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T20:09:35Z","timestamp":1586376575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02023002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["BF02023002"],"URL":"https:\/\/doi.org\/10.1007\/bf02023002","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}