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

DOI10.1007/s10878-011-9437-8zbMath1275.90084OpenAlexW1996872016MaRDI 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 optimizationtabu searchmaximum cliqueconstrained neighborhoodinformed restart

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (21)

Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata ⋮ A review on algorithms for maximum clique problems ⋮ A three-phased local search approach for the clique partitioning problem ⋮ 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 ⋮ Breakout local search for maximum clique problems ⋮ A new exact maximum clique algorithm for large and massive sparse graphs ⋮ An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ A Metaheuristic Approach for an Optimized Design of a Silicon Carbide Operational Amplifier ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ Multi-neighborhood tabu search for the maximum weight clique problem ⋮ A branch-and-cut algorithm for the edge interdiction clique problem ⋮ Team selection for prediction tasks ⋮ 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 ⋮ An enhanced bitstring encoding for exact maximum clique search in sparse graphs

Uses Software

• QUALEX
• EXTRACOL
• DIMACS
• Tabu search

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An adaptive multistart tabu search approach to solve the maximum clique problem