Some experiments with simulated annealing for coloring graphs. (English) Zbl 0626.90067

Methods of thermodynamical simulation have been used for several famous combinatorial optimization problems. For graph coloring (i.e. partition of the node set into as few independent sets as possible) we describe a method of simulation. Such an approach is combined with other techniques for graph coloring. Experiments on random graphs show evidence that this combination gives better results than anyone of the original non-combined methods.


90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
05C15 Coloring of graphs and hypergraphs
90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Bonomi, E.; Lutton, J. L., The \(N\)-city travelling salesman problem statistical mechanics and the Metropolis algorithm, SIAM Review, 26, 551-568 (1984) · Zbl 0551.90095
[2] Brélaz, D., New methods to color the vertices of a graph, Communications of the Association for Computer Machinery, 22, 251-256 (1979) · Zbl 0394.05022
[3] Burkard, R. E.; Rendl, F., A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal of Operational Research, 17, 169-174 (1984) · Zbl 0541.90070
[4] Garey, M. R.; Johnson, D. S., (Computers and Intractability (1979), Freeman: Freeman New York) · Zbl 0411.68039
[5] Hajek, B., Cooling schedules for optimal annealing (1985), Department of electrical Engineering and the coordinated science Laboratory, University of Illinois at Champaign-Urbana: Department of electrical Engineering and the coordinated science Laboratory, University of Illinois at Champaign-Urbana San Francisco · Zbl 0652.65050
[6] Hansen, P.; Delattre, M., Complete-link cluster analysis by graph coloring, Journal of the American Statistical Association, 73, 397-403 (1978) · Zbl 0432.05004
[7] Johnson D.S., Private communication.; Johnson D.S., Private communication.
[8] Johri, A.; Matula, D. W., Probabilistic bounds and heuristic algorithms for coloring large random graphs (1982), Southern Methodist University: Southern Methodist University Dallas, Texas
[9] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[10] Kumar, K. R.; Kusiak, A.; Vanelli, A., Grouping of parts and components in flexible manufacturing systems, European Journal of Operational Research, 24, 387-397 (1986) · Zbl 0599.90048
[11] Leighton, F. T., A graph coloring algorithm for large scheduling problems, Journal of Research of the National Bureau of Standards, 84, 489-503 (1979) · Zbl 0437.68021
[12] Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A., Equation of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1092 (1953) · Zbl 1431.65006
[13] Stecke, K., Design planning, scheduling and control problems of flexible manufacturing problems, Annals of Operations Research, 3, 3-12 (1985)
[14] Werra D., de, An introduction to timetabling, European Journal of Operational Research, 19, 151-162 (1985) · Zbl 0553.90059
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.