STABULUS: A technique for finding stable sets in large graphs with tabu search. (English) Zbl 0685.68056

Summary: Numerical experiments with tabu search have been carried out for constructing independent sets in large graphs. We present some variations on the independent set problem and discuss the results obtained by the tabu search technique. As for graph coloring, this method seems to be a very efficient heuristic procedure.


68P10 Searching and sorting
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Balas, E., Yu, C.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput.15, 1054–1068 (1986). · Zbl 0604.05024 · doi:10.1137/0215075
[2] Berge, C.: Graphes. Paris: Gauthier-Villars 1983.
[3] Bollobàs, B., Thomason, A.: Random graphs of small order, Random graphs ’83. Annals of Discrete Mathematics28, 47–97 (1985). · Zbl 0588.05040
[4] Chams, M., Hertz, A., de Werra, D.: Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research32, 260–266 (1987). · Zbl 0626.90067 · doi:10.1016/S0377-2217(87)80148-0
[5] Glover, F.: Tabu search. Paper presented at ORSA/TIMS meeting, St. Louis, Mo (1987).
[6] Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers and Operations Research13, 533–549 (1986). · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[7] Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. Computing39, 345–351 (1987). · Zbl 0626.68051 · doi:10.1007/BF02239976
[8] Johnson, D. S., Yannakakis, M., Papadimitriou, C. H.: On generating all maximal independent sets. Information Processing Letters27, 119–123 (1988). · Zbl 0654.68086 · doi:10.1016/0020-0190(88)90065-8
[9] Johri, A., Matula, D. W.: Probabilistic bounds and heuristic algorithms for coloring large random graphs. Southern Methodist University, Dallas, Texas (1982).
[10] Leighton, F.: A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards84, 489–503 (1979). · Zbl 0437.68021
[11] Loukakis, E.: A new backtracking algorithm for generating the family of maximal independent sets of a graph. Computer and Mathematics with Applications9, 583–589 (1983). · Zbl 0528.05058 · doi:10.1016/0898-1221(83)90115-3
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.