Some experiments with simulated annealing for coloring graphs
From MaRDI portal
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.
Recommendations
Cites work
- A graph coloring algorithm for large scheduling problems
- A thermodynamically motivated simulation procedure for combinatorial optimization problems
- An introduction to timetabling
- Cooling Schedules for Optimal Annealing
- Equation of state calculations by fast computing machines
- Grouping of parts and components in flexible manufacturing systems
- scientific article; zbMATH DE number 3672307 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- New methods to color the vertices of a graph
- Optimization by simulated annealing
- The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
Cited in
(52)- A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing
- Combinatorial optimization in system configuration design
- A search space ``cartography for guiding graph coloring heuristics
- On a parallel genetic-tabu search based algorithm for solving the graph colouring problem
- A memetic algorithm for graph coloring
- Tabu search techniques. A tutorial and an application to neural networks
- COSINE: A new graph coloring algorithm
- STABULUS: A technique for finding stable sets in large graphs with tabu search
- An SA/TS mixture algorithm for the scheduling tardiness problem
- General local search methods
- The life span method -- a new variant of local search
- Local optima topology for the \(k\)-coloring problem
- A robust simulated annealing based examination timetabling system.
- A variable neighborhood search for graph coloring.
- A wide-ranging computational comparison of high-performance graph colouring algorithms
- Coloring large graphs based on independent set extraction
- An information-based neural approach to generic constraint satisfaction.
- Variants of simulated annealing for the examination timetabling problem
- Genetic and hybrid algorithms for graph coloring
- Metaheuristics: A bibliography
- Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
- Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph.
- An incremental search heuristic for coloring vertices of a graph
- On the use of some known methods for \(T\)-colorings of graphs
- Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm
- Simple decentralized graph coloring
- A graph coloring heuristic using partial solutions and a reactive tabu scheme
- CHECKCOL: improved local search for graph coloring
- Coloring graphs by iterated local search traversing feasible and infeasible solutions
- An adaptive memory algorithm for the k-coloring problem
- An improved ant colony optimisation heuristic for graph colouring
- Embedding a novel objective function in a two-phased local search for robust vertex coloring
- A survey of local search methods for graph coloring
- A review on algorithms for maximum clique problems
- Simulated annealing and graph colouring
- Informed reactive tabu search for graph coloring
- An extraction and expansion approach for graph coloring
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Heuristics for a project management problem with incompatibility and assignment costs
- Quantum annealing of the graph coloring problem
- scientific article; zbMATH DE number 597813 (Why is no real title available?)
- Simulated annealing and its problems to color graphs
- scientific article; zbMATH DE number 2166875 (Why is no real title available?)
- Hybrid evolutionary algorithm for the b-chromatic number
- Using tabu search techniques for graph coloring
- On the chromatic number of graphs
- Hybrid pattern search and simulated annealing for fuzzy production planning problems
- Improving the extraction and expansion method for large graph coloring
- Simulated annealing: A tool for operational research
- Methods for the one-dimensional space allocation problem
- A cooperative search method for the \(k\)-coloring problem
- An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring
This page was built for publication: Some experiments with simulated annealing for coloring graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581241)
