An adaptive multistart tabu search approach to solve the maximum clique problem

DOI10.1007/s10878-011-9437-8zbMath1275.90084MaRDI QIDQ358651

Jin-Kao Hao, Qinghua Wu

Publication date: 9 August 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-011-9437-8

zbMATH Keywords

combinatorial optimization; tabu search; maximum clique; constrained neighborhood; informed restart

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

A Metaheuristic Approach for an Optimized Design of a Silicon Carbide Operational Amplifier, An enhanced bitstring encoding for exact maximum clique search in sparse graphs, Team selection for prediction tasks, An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†, CliSAT: a new exact algorithm for hard maximum clique problems, A three-phased local search approach for the clique partitioning problem, Breakout local search for maximum clique problems, A new exact maximum clique algorithm for large and massive sparse graphs, Detecting robust cliques in graphs subject to uncertain edge failures, Clustered maximum weight clique problem: algorithms and empirical analysis, Frequency-driven tabu search for the maximum \(s\)-plex problem, Multi-neighborhood tabu search for the maximum weight clique problem, A new branch-and-bound algorithm for the maximum weighted clique problem, A branch-and-cut algorithm for the edge interdiction clique problem, An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network, An opposition-based memetic algorithm for the maximum quasi-clique problem, A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems, SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem, A new branch-and-bound algorithm for the maximum edge-weighted clique problem, A review on algorithms for maximum clique problems, Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata

Uses Software

• QUALEX
• EXTRACOL
• DIMACS
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch and cut solver for the maximum stable set problem
• An exact algorithm for the maximum clique problem
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• Reactive and dynamic local search for max-clique: engineering effective building blocks
• An effective local search for the maximum clique problem
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• The maximum clique problem
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• A fast algorithm for the maximum clique problem
• Coloring large graphs based on independent set extraction
• An effective heuristic algorithm for sum coloring of graphs
• A novel evolutionary formulation of the maximum independent set problem
• Hybrid evolutionary algorithms for graph coloring
• Solving the maximum clique problem using a tabu search approach
• Phased local search for the maximum clique problem
• A new trust region technique for the maximum weight clique problem
• A hybrid heuristic for the maximum clique problem
• Finding a Maximum Clique in an Arbitrary Graph
• Reducibility among Combinatorial Problems
• Reactive local search for the maximum clique problem