Subgraph extraction and metaheuristics for the maximum clique problem

DOI10.1007/S10732-012-9207-5MaRDI QIDQ2359135zbMATH OpenOpenAlexFDO

Authors Duc-Cuong Dang, A. Moukrim

Publication date 27 June 2017

Published in Journal of Heuristics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10732-012-9207-5

zbMATH Keywords

metaheuristicsgenetic algorithmiterated local searchmaximum clique problemcircular-arc graphtriangulated graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Applications of mathematical programming (90C90) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A hybrid heuristic for the maximum clique problem
• An adaptive multistart tabu search approach to solve the maximum clique problem
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• A scatter search algorithm for the maximum clique problem
• A New Approach for Solving the Maximum Clique Problem

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 5547826 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 939919 (Why is no real title available?)
• A hybrid heuristic for the maximum clique problem
• A new trust region technique for the maximum weight clique problem
• A study of ACO capabilities for solving the maximum clique problem
• Algorithmic graph theory and perfect graphs
• An effective local search for the maximum clique problem
• An exact algorithm for the maximum clique problem
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• Error detecting and error correcting codes
• Finding a Maximum Clique in an Arbitrary Graph
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
• Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems
• Phased local search for the maximum clique problem
• Reactive local search for the maximum clique problem
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• Test case generators and computational results for the maximum clique problem
• The maximum clique problem
• Variable neighborhood search for the maximum clique

Cited in

(6)

• Hybridizations of evolutionary algorithms with large neighborhood search
• The clustered team orienteering problem
• Performance evaluation of a parallel ant colony optimization for the real-time train routing selection problem in large instances
• Solving the team orienteering problem with cutting planes
• A hybrid heuristic for the maximum clique problem
• Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms

Describes a project that uses

Uses Software

• DIMACS
• BHOSLIB
• QUALEX

This page was built for publication: Subgraph extraction and metaheuristics for the maximum clique problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359135)