×
Friden, C.; Hertz, A.; de Werra, Dominique

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

Computing 42, No. 1, 35-44 (1989).
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.

Cited in 34 Documents

MSC:

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

Keywords:

timetabling; tabu search; independent set problem; heuristic procedure
PDF BibTeX XML Cite
\textit{C. Friden} et al., Computing 42, No. 1, 35--44 (1989; Zbl 0685.68056)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Balas, E., Yu, C.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput.15, 1054–1068 (1986). · Zbl 0604.05024
[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
[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
[7] Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. Computing39, 345–351 (1987). · Zbl 0626.68051
[8] Johnson, D. S., Yannakakis, M., Papadimitriou, C. H.: On generating all maximal independent sets. Information Processing Letters27, 119–123 (1988). · Zbl 0654.68086
[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
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.