STABULUS: A technique for finding stable sets in large graphs with tabu search

DOI10.1007/BF02243141zbMath0685.68056OpenAlexW1555834419MaRDI QIDQ1262136

Dominique de Werra, C. Friden, Alain Hertz

Publication date: 1989

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02243141

zbMATH Keywords

tabu searchtimetablingindependent set problemheuristic procedure

Mathematics Subject Classification ID

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

Related Items (37)

Solving the maximum clique problem using a tabu search approach ⋮ Genetic algorithms and tabu search: Hybrids for optimization ⋮ A review on algorithms for maximum clique problems ⋮ Solving transportation problems with nonlinear side constraints with tabu search ⋮ Polynomially solvable cases for the maximum stable set problem ⋮ Detecting robust cliques in graphs subject to uncertain edge failures ⋮ The tabu search metaheuristic: How we used it ⋮ Clustered maximum weight clique problem: algorithms and empirical analysis ⋮ Breakout local search for maximum clique problems ⋮ An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ An adaptive multistart tabu search approach to solve 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 ⋮ A new extension of local search applied to the Dial-A-Ride problem ⋮ A new binary (17,4,5) constant weight code ⋮ A variable neighborhood search for graph coloring. ⋮ A New Composite Algorithm for Clustering Problems ⋮ A branch-and-price algorithm for the robust graph coloring problem ⋮ A cooperative search method for the \(k\)-coloring problem ⋮ Essential particle swarm optimization queen with tabu search for MKP resolution ⋮ Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling ⋮ Multi-neighborhood tabu search for the maximum weight clique problem ⋮ A survey of local search methods for graph coloring ⋮ A study of ACO capabilities for solving the maximum clique problem ⋮ Mining relevant information on the Web: a clique-based approach ⋮ Learning driven three-phase search for the maximum independent union of cliques problem ⋮ EPCOT: An efficient procedure for coloring optimally with Tabu Search ⋮ Greedy randomized adaptive search procedures ⋮ A metaheuristic algorithm for large maximum weight independent set problems ⋮ TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph ⋮ The life span method -- a new variant of local search ⋮ An efficient tabu search procedure for the \(p\)-median problem ⋮ Constructing a course schedule by solving a series of assignment type problems ⋮ The maximum clique problem ⋮ A tabu search algorithm for finding good forest harvest schedules satisfying green-up constraints

Cites Work

• Unnamed Item
• Using tabu search techniques for graph coloring
• Some experiments with simulated annealing for coloring graphs
• A new backtracking algorithm for generating the family of maximal independent sets of a graph
• On generating all maximal independent sets
• Future paths for integer programming and links to artificial intelligence
• Finding a Maximum Clique in an Arbitrary Graph
• A graph coloring algorithm for large scheduling problems

This page was built for publication: STABULUS: A technique for finding stable sets in large graphs with tabu search