An effective local search for the maximum clique problem

DOI10.1016/j.ipl.2005.05.010zbMath1185.68283OpenAlexW2108455025WikidataQ56210425 ScholiaQ56210425MaRDI QIDQ1041822

Akihiro Hamamoto, Hiroyuki Narihisa, Kengo Katayama

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.05.010

zbMATH Keywords

combinatorial optimizationgraph algorithmsneighborhoodmaximum clique problemvariable depth search

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Subgraph extraction and metaheuristics for the maximum clique problem ⋮ Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata ⋮ A review on algorithms for maximum clique problems ⋮ Breakout local search for maximum clique problems ⋮ An adaptive multistart tabu search approach to solve the maximum clique problem ⋮ Finding near-optimal independent sets at scale ⋮ Reinforcement learning for combinatorial optimization: a survey ⋮ Solving maximum clique problem using chemical reaction optimization ⋮ Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds ⋮ SQBC: an efficient subgraph matching method over large and dense graphs ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique ⋮ A simple simulated annealing algorithm for the maximum clique problem ⋮ An efficient local search for the feedback vertex set problem ⋮ Fast local search for the maximum independent set problem ⋮ Multi-neighborhood tabu search for the maximum weight clique problem ⋮ On the independent set problem in random graphs ⋮ Simple ingredients leading to very efficient heuristics for the maximum clique problem

Uses Software

• Max-AO
• DIMACS
• Tabu search

Cites Work

• Maximum stable set formulations and heuristics based on continuous optimization
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Evolutionary computing
• Annealed replication: A new heuristic for the maximum clique problem
• Greedy and local search heuristics for unconstrained binary quadratic programming
• Combining the scalability of local search with the pruning techniques of systematic search
• Chained Lin-Kernighan for Large Traveling Salesman Problems
• An Efficient Heuristic Procedure for Partitioning Graphs
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Reactive local search for the maximum clique problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item