A review on algorithms for maximum clique problems
From MaRDI portal
Publication:2630214
DOI10.1016/j.ejor.2014.09.064zbMath1341.05241OpenAlexW2037016941MaRDI QIDQ2630214
Publication date: 26 July 2016
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://hal.univ-angers.fr/hal-02709508/file/maxcliquereview07oct2014fv.pdf
Programming involving graphs or networks (90C35) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Approximation methods and heuristics in mathematical programming (90C59) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
The triangle \(k\)-club problem, An SDP-based approach for computing the stability number of a graph, A new family of facet defining inequalities for the maximum edge-weighted clique problem, BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, Minimum cost edge blocker clique problem, Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata, Solving the maximum vertex weight clique problem via binary quadratic programming, Detecting robust cliques in graphs subject to uncertain edge failures, Finding disjoint dense clubs in a social network, Boosting ant colony optimization via solution prediction and machine learning, Fast Cluster Detection in Networks by First Order Optimization, On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem, Clustered maximum weight clique problem: algorithms and empirical analysis, Frequency-driven tabu search for the maximum \(s\)-plex problem, A variable neighborhood search heuristic for the maximum ratio clique problem, Infra-chromatic bound for exact maximum clique search, Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph, An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network, Finding near-optimal independent sets at scale, Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation, Online summarization of dynamic graphs using subjective interestingness for sequential data, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, The stable set problem: clique and nodal inequalities revisited, General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem, BDD-based optimization for the quadratic stable set problem, A post-quantum associative memory, The exam location problem: mathematical formulations and variants, On maximum ratio clique relaxations, Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks, On designing networks resilient to clique blockers, A General Regularized Continuous Formulation for the Maximum Clique Problem, The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study, hClique: An exact algorithm for maximum clique problem in uniform hypergraphs, Maximum independent sets and supervised learning, A new binary (17,4,5) constant weight code, CliSAT: a new exact algorithm for hard maximum clique problems, A greedy algorithm to construct covering arrays using a graph representation, Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications, Incremental Upper Bound for the Maximum Clique Problem, A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique, Finding Disjoint Dense Clubs in an Undirected Graph, Parallelization of a branch-and-bound algorithm for the maximum weight clique problem, Differentially private nearest neighbor classification, Frank-Wolfe and friends: a journey into projection-free first-order optimization methods, Generalization of machine learning for problem reduction: a case study on travelling salesman problems, An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem, Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks, Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs, Effective metaheuristic algorithms for the minimum differential dispersion problem, Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem, General cut-generating procedures for the stable set polytope, PUSH: A generalized operator for the maximum vertex weight clique problem, Dominant-set clustering: a review, A new upper bound for the maximum weight clique problem, A parallel maximum clique algorithm for large and massive sparse graphs, A nonconvex quadratic optimization approach to the maximum edge weight clique problem, A new branch-and-bound algorithm for the maximum weighted clique problem, Polyhedral properties of the induced cluster subgraphs, A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming, Computing maximum \(k\)-defective cliques in massive graphs, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, A characterization of the weighted Lovász number based on convex quadratic programming, A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem, A maximum edge-weight clique extraction algorithm based on branch-and-bound, Correlation between the continuous-time quantum walk and cliques in graphs and its application, Dynamic node packing, An enhanced bitstring encoding for exact maximum clique search in sparse graphs
Uses Software
Cites Work
- A branch-and-cut algorithm for the maximum cardinality stable set problem
- Reactive local search for the maximum clique problem
- Fast heuristics for large scale covering-location problems
- Adaptive, restart, randomized greedy heuristics for maximum clique
- Different Formulations for Solving the HeaviestK-Subgraph 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- DIMACS
- Breakout local search for maximum clique problems
- An adaptive multistart tabu search approach to solve the maximum clique problem
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- The \textsc{max quasi-independent set} problem
- Graph clustering
- A branch and cut solver for the maximum stable set problem
- Fast local search for the maximum independent set problem
- Some experiments with simulated annealing for coloring graphs
- Local search with edge weighting and configuration checking heuristics for minimum vertex cover
- Variable neighborhood search for the maximum clique
- An exact bit-parallel algorithm for the maximum clique problem
- A branch-and-bound approach for maximum quasi-cliques
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- Solving group technology problems via clique partitioning
- An exact algorithm for the maximum clique problem
- Black box scatter search for general classes of binary optimization problems
- Approximating the maximum vertex/edge weighted clique using local search
- Simple ingredients leading to very efficient heuristics for the maximum clique problem
- A heuristic approach for the max-min diversity problem based on max-clique
- Variable neighborhood search for the heaviest \(k\)-subgraph
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Reactive and dynamic local search for max-clique: engineering effective building blocks
- An effective local search for the maximum clique problem
- A method for member selection of cross-functional teams using the individual and collaborative performances
- An iterative approach to robust and integrated aircraft routing and crew scheduling
- Dual quadratic estimates in polynomial and Boolean programming
- STABULUS: A technique for finding stable sets in large graphs with tabu search
- Classifying molecular sequences using a linkage graph with their pairwise similarities
- An extended formulation approach to the edge-weighted maximal clique problem
- A cutting-plane approach to the edge-weighted maximal clique problem
- The maximum clique problem
- Maximum stable set formulations and heuristics based on continuous optimization
- New facets and a branch-and-cut algorithm for the weighted clique problem.
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- A fast algorithm for the maximum clique problem
- Exact algorithms for maximum clique: a computational study
- Multi-threading a state-of-the-art maximum clique algorithm
- On the maximum quasi-clique problem
- Multi-neighborhood tabu search for the maximum weight clique problem
- Coloring large graphs based on independent set extraction
- Cliques with maximum/minimum edge neighborhood and neighborhood density
- An effective heuristic algorithm for sum coloring of graphs
- An augmentation algorithm for the maximum weighted stable set problem
- An application of tabu search heuristic for the maximum edge-weighted subgraph problem
- Towards optimal lower bounds for clique and chromatic number.
- Genetic and hybrid algorithms for graph coloring
- An improved bit parallel exact maximum clique algorithm
- Speeding up branch and bound algorithms for solving the maximum clique problem
- Iterated greedy for the maximum diversity problem
- A hybrid metaheuristic method for the maximum diversity problem
- Solving the maximum clique problem using a tabu search approach
- Phased local search for the maximum clique problem
- A branch and bound algorithm for the maximum diversity problem
- Iterated tabu search for the maximum diversity problem
- A new trust region technique for the maximum weight clique problem
- A hybrid heuristic for the maximum clique problem
- A study of ACO capabilities for solving the maximum clique problem
- Mining market data: a network approach
- Hybrid heuristics for the maximum diversity problem
- Extended and discretized formulations for the maximum clique problem
- Approximation Algorithms for Dispersion Problems
- A Complementary Pivoting Approach to the Maximum Weight Clique Problem
- Fixed-Parameter and Approximation Algorithms: A New Look
- Clique Relaxation Models in Social Network Analysis
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
- Design and Implementation of an Interactive Optimization System for Telephone Network Planning
- Vertex packings: Structural properties and algorithms
- New methods to color the vertices of a graph
- Heuristic and Special Case Algorithms for Dispersion Problems
- Greedy and heuristic algorithms for codes and colorings
- Hyper-Heuristics: An Emerging Direction in Modern Search Technology
- Approximating Maximum Clique by Removing Subgraphs
- Extended clique initialisation in examination timetabling
- Exact and Approximation Algorithms for Densest k-Subgraph
- A tutorial on branch and cut algorithms for the maximum stable set problem
- Reducibility among Combinatorial Problems
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Experimental and Efficient Algorithms
- Principles and Practice of Constraint Programming – CP 2003
- A branch and bound algorithm for the maximum clique problem
- The dense \(k\)-subgraph problem