×
Gendreau, Michel; Soriano, Patrick; Salvail, Louis

Solving the maximum clique problem using a tabu search approach. (English) Zbl 0775.90297

Ann. Oper. Res. 41, No. 1-4, 385-403 (1993).

Cited in 35 Documents

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Software:

TABARIS; Algorithm 457
PDF BibTeX XML Cite
\textit{M. Gendreau} et al., Ann. Oper. Res. 41, No. 1--4, 385--403 (1993; Zbl 0775.90297)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] G. Avondo-Bodeno,Economic Applications of the Theory of Graphs (Gordon and Breach, New York, 1962).
[2] L. Babel, Finding maximum cliques in arbitrary and in special graphs, Report TUM-M9008, Mathematisches Institut und Institut für Informatik, Technische Universität München (1990), to appear in Computing.
[3] L. Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem, Zeits. Oper. Res. 34(1990)207–217. · Zbl 0701.90091
[4] 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–221. · Zbl 0722.68086
[5] E. Balas and C.S Yu, Finding a maximum clique in an arbitrary graph, SIAM J. Comput. 15(1986)1054–1068. · Zbl 0604.05024
[6] C. Berge,Théorie des Graphes et ses Applications (Dunod, Paris, 1962).
[7] B. Bollobas,Random Graphs (Academic Press, London, 1985).
[8] B. Bollobas and P. Erdös, Cliques in random graphs, Math. Proc. Camb. Phil. Soc. 80(1976)419–427. · Zbl 0344.05155
[9] C. Bron and J. Kerbosch, Finding all cliques of an undirected graph, Comm. ACM 16(1973)575–577. · Zbl 0261.68018
[10] R. Carraghan and P.M. Pardalos, An exact algorithm for the maximum clique problem, Oper. Res. Lett. 9(1990)375–382. · Zbl 0711.90080
[11] V. Degot and J.M. Hualde, De l’utilisation de la notion de clique (sous-graphe complet symétrique) en matière de typologie des populations, Revue française d’automatique et recherche opérationelle: Recherche opérationelle 9(1975)5–18. · Zbl 0303.68028
[12] N. Deo,Graph Theory with Applications to Engineering and Computer Science (Prentice-Hall, Englewood Cliffs, 1974). · Zbl 0285.05102
[13] C. Ebenegger, P.L. Hammer and D. de Werra, Pseudo-Boolean functions and stability of graphs, Ann. Discr. Math. 19(1984)83–98. · Zbl 0567.05031
[14] 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–44. · Zbl 0685.68056
[15] 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–445. · Zbl 0713.90087
[16] M.R. Garey and D.S. Johnson,Computers and Intractibility: a Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). · Zbl 0411.68039
[17] M. Gendreau, A fast greedy algorithm for the maximum clique problem, paper presented at the TIMS/ORSA Meeting, New Orleans (May 1987).
[18] 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). · Zbl 0648.90083
[19] M. Gendreau, L. Salvail and P. Soriano, An appraisal of greedy heuristics for the maximum clique problem, Centre de Recherche sur les Transports, Université de Montréal, forthcoming.
[20] M. Gendreau, P. Soriano and L. Salvail, Simulated annealing and cliques, Centre de Recherche sur les Transports, Université de Montréal, forthcoming; paper presented at the ORSA/TIMS Meeting, New York (October 1989).
[21] L. Gerhards and W. Lindenberg, Clique detection for nondirected graphs: two new algorithms, Computing 21 (1979)295–322. · Zbl 0441.68073
[22] F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res. 13(1986)533–549. · Zbl 0615.90083
[23] F. Glover, Tabu search. Part I, ORSA J. Comput. 1(1989)190–206.
[24] F. Glover, Tabu search. Part II, ORSA J. Comput. 2(1990)4–32.
[25] J.W. Greene and K.J. Supowit, Simulated annealing without rejected moves, IEEE Trans. Comput. Aided Des. CAD-5(1986)221–228. · Zbl 05448148
[26] M. Grötschel, L. Lovasz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988). · Zbl 0634.05001
[27] P. Hansen and B. Jaumard, Algorithms for the maximum satisfiability problem, RUTCOR Research Report 43–87, Rutgers University (1987). · Zbl 0716.68077
[28] 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). · Zbl 0224.05129
[29] A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 29(1987)345–351. · Zbl 0626.68051
[30] D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci. 9(1974)256–278. · Zbl 0296.65036
[31] D.S. Johnson, M. Yannakakis and C.H. Papadimitriou, On generating all maximal independent sets, Inf. Proc. Lett. 27(1988)119–123. · Zbl 0654.68086
[32] S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983)671–680. · Zbl 1225.90162
[33] E. Loukakis, A new backtracking algorithm for generating the family of maximal independent sets of a graph, Comput. Math. Appl. 9(1983)583–589. · Zbl 0528.05058
[34] E. Loukakis and C. Tsouros, Determining the number of internal stability of a graph, Int. J. Comput. Math. 11(1982)207–220. · Zbl 0496.05057
[35] D.W. Matula, The employee party problem, Not. A.M.S. 19(1972)A-382.
[36] D.W. Matula, The largest clique in a random graph, Technical Report CS7608, Southern Methodist University (1976).
[37] D.W. Matula, Expose-and-merge exploration and the chromatic number of a random graph, Combinatorica 7(1987)275–284. · Zbl 0648.05049
[38] 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–175. · Zbl 0723.68085
[39] P.M. Pardalos and A. Phillips, A global optimization approach for solving the maximum clique problem, Int. J. Comput. Math. 33((1990)209–216. · Zbl 0825.68488
[40] P.M. Pardalos and G.P. Rodgers, A branch and bound algorithm for the maximum clique problem, Comp. Oper. Res. 19(1992)363–375. · Zbl 0757.90082
[41] J.M. Robson, Algorithms for the maximum independent sets, J. Algor. 7(1986)425–440. · Zbl 0637.68080
[42] B. Roy,Algèbre Moderne et Théorie des Graphes, Vol. 1 (Dunod, Paris, 1969). · Zbl 0238.90072
[43] C.E. Shannon, The zero-error capacity of a noisy channel,Symp. on Information Theory, I.R.E. Trans. 3(1956).
[44] R.E. Tarjan and A.E. Trojanowski, Finding a maximum independent set, SIAM J. Comput. 6(1977)537–546. · Zbl 0357.68035
[45] J. Turner and W.H. Kautz, A survey of progress in graph theory in the Soviet Union, SIAM 12(1970). · Zbl 0201.56702
[46] D. de Werra and A. Hertz, Tabu search techniques: A tutorial and application to neural networks, OR Spektrum 11(1989)131–141. · Zbl 0672.90089
[47] M. Widmer and A. Hertz, A new heuristic method for solving the flow shop sequencing problem, Eur. J. Oper. Res. 41(1989)186–193. · Zbl 0671.90040
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.