Using tabu search techniques for graph coloring
From MaRDI portal
Publication:580987
DOI10.1007/BF02239976zbMath0626.68051OpenAlexW2168000780MaRDI QIDQ580987
Dominique de Werra, Alain Hertz
Publication date: 1987
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02239976
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
Chromatic scheduling and frequency assignment ⋮ Local optima topology for the \(k\)-coloring problem ⋮ Hybrid evolutionary search for the minimum sum coloring problem of graphs ⋮ A parallel tabu search algorithm for large traveling salesman problems ⋮ A user's guide to tabu search ⋮ An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search ⋮ Part type selection problem in flexible manufacturing systems: Tabu search algorithms ⋮ On the use of some known methods for \(T\)-colorings of graphs ⋮ Solving the maximum clique problem using a tabu search approach ⋮ A graph partitioning heuristic for the parallel pseudo-exhaustive logical test of VLSI combinational circuits ⋮ Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search ⋮ Graph colouring approaches for a satellite range scheduling problem ⋮ Genetic algorithms and tabu search: Hybrids for optimization ⋮ Circular coloring of graphs via linear programming and tabu search ⋮ Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm ⋮ The tabu search metaheuristic: How we used it ⋮ New secure partial encryption method for medical images using graph coloring problem ⋮ A memetic algorithm for the minimum sum coloring problem ⋮ Online algorithms for the maximum \(k\)-colorable subgraph problem ⋮ Compromise ratio with weighting functions in a tabu search multi-criteria approach to examination timetabling ⋮ New approaches for heuristic search: A bilateral linkage with artificial intelligence ⋮ Simple decentralized graph coloring ⋮ Solution techniques for the large set covering problem ⋮ Semidefinite programming relaxations for graph coloring and maximal clique problems ⋮ A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding ⋮ Common due-date determination and sequencing using tabu search ⋮ A comparison of neighborhood search techniques for multi-objective combinatorial problems ⋮ Tabu search techniques. A tutorial and an application to neural networks ⋮ Diversification strategies in tabu search algorithms for the maximum clique problem ⋮ Tabu search for graph partitioning ⋮ Genetic and hybrid algorithms for graph coloring ⋮ Metaheuristics: A bibliography ⋮ Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs ⋮ An effective hybrid algorithm for university course timetabling ⋮ Modelling constant weight codes using tabu search ⋮ Tabu search for the BWC problem ⋮ Heuristics for biquadratic assignment problems and their computational comparison ⋮ A new extension of local search applied to the Dial-A-Ride problem ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ Adaptive feasible and infeasible tabu search for weighted vertex coloring ⋮ Heuristics for a project management problem with incompatibility and assignment costs ⋮ An exact approach for the vertex coloring problem ⋮ Quantum annealing of the graph coloring problem ⋮ A variable neighborhood search for graph coloring. ⋮ Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable ⋮ Simulated annealing: A tool for operational research ⋮ Using tabu search with longer-term memory and relaxation to create examination timetables. ⋮ Multi-coloring and job-scheduling with assignment and incompatibility costs ⋮ A cooperative search method for the \(k\)-coloring problem ⋮ A graph coloring heuristic using partial solutions and a reactive tabu scheme ⋮ COSINE: A new graph coloring algorithm ⋮ A sequential elimination algorithm for computing bounds on the clique number of a graph ⋮ CHECKCOL: improved local search for graph coloring ⋮ Artificial life techniques for load balancing in computational grids ⋮ Exchanges procedures for timetabling problems ⋮ Finding a feasible course schedule using Tabu search ⋮ A semidefinite programming-based heuristic for graph coloring ⋮ An ant-based algorithm for coloring graphs ⋮ Coloring graphs by iterated local search traversing feasible and infeasible solutions ⋮ Another look at graph coloring via propositional satisfiability ⋮ Efficient algorithms for finding critical subgraphs ⋮ An adaptive memory algorithm for the \(k\)-coloring problem ⋮ Location and sizing of offshore platforms for oil exploration ⋮ An improved ant colony optimisation heuristic for graph colouring ⋮ Variable space search for graph coloring ⋮ A mathematical model and a metaheuristic approach for a memory allocation problem ⋮ Hybrid evolutionary algorithm for the b-chromatic number ⋮ Avoiding local optima in the \(p\)-hub location problem using tabu search and GRASP ⋮ Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems ⋮ Consistent neighborhood search for combinatorial optimization ⋮ A tabu search algorithm for structural software testing ⋮ A wide-ranging computational comparison of high-performance graph colouring algorithms ⋮ Embedding a novel objective function in a two-phased local search for robust vertex coloring ⋮ Coloring large graphs based on independent set extraction ⋮ A new \textsf{DSATUR}-based algorithm for exact vertex coloring ⋮ About equivalent interval colorings of weighted graphs ⋮ Using local search to speed up filtering algorithms for some NP-hard constraints ⋮ An exact method for graph coloring ⋮ An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring ⋮ Improving the extraction and expansion method for large graph coloring ⋮ A tabu search algorithm for the routing and capacity assignment problem in computer networks ⋮ A hybrid heuristic for the maximum dispersion problem ⋮ EPCOT: An efficient procedure for coloring optimally with Tabu Search ⋮ A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing ⋮ STABULUS: A technique for finding stable sets in large graphs with tabu search ⋮ TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph ⋮ Optimizing tabu list size for the traveling salesman problem ⋮ A simple tabu search method to solve the mixed-integer linear bilevel programming problem ⋮ An incremental search heuristic for coloring vertices of a graph ⋮ General local search methods ⋮ The life span method -- a new variant of local search ⋮ Combinatorial optimization in system configuration design ⋮ An efficient memetic algorithm for the graph partitioning problem ⋮ An efficient tabu search procedure for the \(p\)-median problem ⋮ Driving tabu search with case-based reasoning ⋮ Graph coloring by multiagent fusion search ⋮ 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 for large scale timetabling problems ⋮ Lower Bounds for the Minimal Sum Coloring Problem ⋮ A Novel Approach for Detecting Relationships in Social Networks Using Cellular Automata Based Graph Coloring ⋮ Three tabu search methods for the MI-FAP applied to 802.11 networks ⋮ Iterative coloring extension of a maximum clique ⋮ A Tabu Search Heuristic for the Equitable Coloring Problem ⋮ SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning ⋮ A systematic study on meta-heuristic approaches for solving the graph coloring problem ⋮ Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems ⋮ A massively parallel evolutionary algorithm for the partial Latin square extension problem ⋮ A memetic algorithm for deinterleaving pulse trains ⋮ Monte Carlo tree search with adaptive simulation: a case study on weighted vertex coloring ⋮ Heuristics from Nature for Hard Combinatorial Optimization Problems ⋮ Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints ⋮ Graph Coloring Models and Metaheuristics for Packing Applications ⋮ A survey on vertex coloring problems ⋮ Simulated annealing: An introduction ⋮ Optimizing the system of virtual paths by tabu search. ⋮ A tabu search procedure based on a random roulette diversification for the weighted maximal planar graph problem ⋮ A survey of local search methods for graph coloring ⋮ A branch-and-cut algorithm for graph coloring ⋮ Unnamed Item ⋮ A NEW APPROACH TO THE VERTEX COLORING PROBLEM ⋮ Adaptive memory programming: a unified view of metaheuristics ⋮ Parallel Immune System for Graph Coloring ⋮ On the recursive largest first algorithm for graph colouring ⋮ Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation ⋮ INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING ⋮ AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING
Cites Work