A fast algorithm for the maximum clique problem

From MaRDI portal

Publication:1613374

Jump to:navigation, search

DOI10.1016/S0166-218X(01)00290-6zbMath1019.05054OpenAlexW2046112356WikidataQ56210432 ScholiaQ56210432MaRDI QIDQ1613374

Patric R. J. Östergård

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00290-6

zbMATH Keywords

branch-and-bound random graphs maximum independent set maximum clique problem DIMACS benchmark graphs

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Parallel Maximum Clique Algorithms with Applications to Network Analysis ⋮ FUZZY ONTOLOGY ALIGNMENT USING BACKGROUND KNOWLEDGE ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ Column elimination for capacitated vehicle routing problems ⋮ Solving the winner determination problem in combinatorial auctions for fractional ownership of autonomous vehicles ⋮ A Max-SAT Inference-Based Pre-processing for Max-Clique ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Independence numbers of Johnson-type graphs ⋮ hClique: An exact algorithm for maximum clique problem in uniform hypergraphs ⋮ Maximum independent sets and supervised learning ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ The maximum volume hard subset model for Poisson processes: simulation aspects ⋮ Algorithms for finding maximum transitive subtournaments ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection ⋮ Orderly generation of Butson Hadamard matrices ⋮ Correlation between the continuous-time quantum walk and cliques in graphs and its application ⋮ Clique algorithms for classifying substructures in generalized quadrangles ⋮ New analytical lower bounds on the clique number of a graph ⋮ Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs ⋮ Quasi-symmetric designs on 56 points ⋮ A polyhedral study of the maximum stable set problem with weights on vertex-subsets ⋮ A review on algorithms for maximum clique problems ⋮ Solving the maximum vertex weight clique problem via binary quadratic programming ⋮ On Dedekind's problem for complete simple games ⋮ Scale reduction techniques for computing maximum induced bicliques ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ Detecting robust cliques in graphs subject to uncertain edge failures ⋮ Approximating 2-cliques in unit disk graphs ⋮ Lower bounding techniques for DSATUR-based branch and bound ⋮ Reducing graph coloring to clique search ⋮ Non-embeddable quasi-residual quasi-symmetric designs ⋮ A logical approach to efficient Max-SAT solving ⋮ A branch-and-check approach for a wind turbine maintenance scheduling problem ⋮ On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ Breakout local search for maximum clique problems ⋮ Infra-chromatic bound for exact maximum clique search ⋮ A new exact maximum clique algorithm for large and massive sparse graphs ⋮ Permutation codes with specified packing radius ⋮ Extended and discretized formulations for the maximum clique problem ⋮ An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments ⋮ An adaptive multistart tabu search approach to solve the maximum clique problem ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem ⋮ On comparing algorithms for the maximum clique problem ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ Metric space method for constructing splitting partitions of graphs ⋮ Algorithms for the maximum \(k\)-club problem in graphs ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ A preemptive bound for the resource constrained project scheduling problem ⋮ Maximum weight relaxed cliques and Russian doll search revisited ⋮ Coloring the nodes of a directed graph ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ On risk-averse maximum weighted subgraph problems ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ An improved bit parallel exact maximum clique algorithm ⋮ SQBC: an efficient subgraph matching method over large and dense graphs ⋮ A greedy algorithm to construct covering arrays using a graph representation ⋮ Incomplete inference for graph problems ⋮ Combinatorial algorithms for the maximum \(k\)-plex problem ⋮ Coordinated cutting plane generation via multi-objective separation ⋮ On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs ⋮ Russian doll search for the Steiner triple covering problem ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ A simple and effective algorithm for the MaxMin diversity problem ⋮ New results on tripod packings ⋮ Optimal \((n,4,2)\)-OOC of small orders. ⋮ Recent advances in vehicle routing exact algorithms ⋮ The sextuply shortened binary Golay code is optimal ⋮ A simple simulated annealing algorithm for the maximum clique problem ⋮ Lower bounds and compact mathematical formulations for spacing soft constraints for university examination timetabling problems ⋮ Exact algorithms for maximum clique: a computational study ⋮ Preprocessing and an improved MIP model for examination timetabling ⋮ A nearly optimal sensor placement algorithm for boundary coverage ⋮ Solving the maximum edge biclique packing problem on unbalanced bipartite graphs ⋮ Decomposing clique search problems into smaller instances based on node and edge colorings ⋮ An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts ⋮ Solving vertex coloring problems as maximum weight stable set problems ⋮ A clique algorithm for standard quadratic programming ⋮ A new compact formulation for the discrete \(p\)-dispersion problem ⋮ PUSH: A generalized operator for the maximum vertex weight clique problem ⋮ A parallel maximum clique algorithm for large and massive sparse graphs ⋮ Finding quasi core with simulated stacked neural networks ⋮ 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 study of the maximum common induced subgraph problem ⋮ On minimum sum representations for weighted voting games ⋮ Coloring large graphs based on independent set extraction ⋮ Cliques with maximum/minimum edge neighborhood and neighborhood density ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ The near resolvable \(2\)-\((13,4,3)\) designs and thirteen-player whist tournaments ⋮ Exploiting semidefinite relaxations in constraint programming ⋮ An exact bit-parallel algorithm for the maximum clique problem ⋮ The clustered team orienteering problem ⋮ Optimal wafer cutting in shuttle layout problems ⋮ A sampling-based exact algorithm for the solution of the minimax diameter clustering problem ⋮ Indirect unstructured hex-dominant mesh generation using tetrahedra recombination ⋮ Cover-encodings of fitness landscapes ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems ⋮ Maximum cut-clique problem: ILS heuristics and a data analysis application ⋮ Discrete Optimization with Decision Diagrams ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ 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 ⋮ Quantum contextuality with stabilizer states ⋮ A branch-and-bound approach for maximum quasi-cliques ⋮ Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation ⋮ Solving robust bin-packing problems with a branch-and-price approach ⋮ Integral point sets over \(\mathbb Z_n^m\) ⋮ A clique search problem and its application to machine scheduling ⋮ A new table of permutation codes ⋮ Miscellaneous classification results for 2-designs ⋮ Estimating clique size by coloring the nodes of auxiliary graphs ⋮ Numerical experiments with LP formulations of the maximum clique problem ⋮ Coloring the edges of a directed graph

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1613374&oldid=13911966"