An exact algorithm for the maximum clique problem

DOI10.1016/0167-6377(90)90057-CzbMath0711.90080OpenAlexW2026320281WikidataQ56210396 ScholiaQ56210396MaRDI QIDQ922964

Panos M. Pardalos, Randy Carraghan

Publication date: 1990

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(90)90057-c

zbMATH Keywords

maximum clique problempartially enumerative algorithmrandomly generated graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (only showing first 100 items - show all)

An Efficient Approximation Algorithm for Finding a Maximum Clique Using Hopfield Network Learning ⋮ A post-quantum associative memory ⋮ A Max-SAT Inference-Based Pre-processing for Max-Clique ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ hClique: An exact algorithm for maximum clique problem in uniform hypergraphs ⋮ Maximum independent sets and supervised learning ⋮ A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Distributed algorithms for maximum cliques ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ A tutorial on branch and cut algorithms for the maximum stable set problem ⋮ A branch and bound algorithm for the maximum clique problem ⋮ Algorithms for finding maximum transitive subtournaments ⋮ On Importance of a Special Sorting in the Maximum-Weight Clique Algorithm Based on Colour Classes ⋮ An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique ⋮ The k-Dense Method to Extract Communities from Complex Networks ⋮ Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection ⋮ Correlation between the continuous-time quantum walk and cliques in graphs and its application ⋮ Clique algorithms for classifying substructures in generalized quadrangles ⋮ An enhanced bitstring encoding for exact maximum clique search in sparse graphs ⋮ A fast algorithm for the maximum clique problem ⋮ Subgraph extraction and metaheuristics for the maximum clique problem ⋮ An exact algorithm for the maximum stable set problem ⋮ A multi-KP modeling for the maximum-clique problem ⋮ Inference of a minimum size Boolean function from examples by using a new efficient branch-and-bound approach ⋮ Solving the maximum clique problem using a tabu search approach ⋮ Minimization of a quadratic pseudo-Boolean function ⋮ Edge coloring of graphs, uses, limitation, complexity ⋮ A review on algorithms for maximum clique problems ⋮ Solving the maximum vertex weight clique problem via binary quadratic programming ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ Detecting robust cliques in graphs subject to uncertain edge failures ⋮ Reducing graph coloring to clique search ⋮ Efficiently enumerating all maximal cliques with bit-parallelism ⋮ An effective and fast heuristic for the dial-a-ride 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 ⋮ Infra-chromatic bound for exact maximum clique search ⋮ 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 ⋮ Permutation codes with specified packing radius ⋮ Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring ⋮ 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 ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ Ramsey theory and integrality gap for the independent set problem ⋮ On the minimum number of logical clauses inferred from examples ⋮ Diversification strategies in tabu search algorithms for the maximum clique problem ⋮ On comparing algorithms for the maximum clique problem ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ Metric space method for constructing splitting partitions of graphs ⋮ Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2 ⋮ The team orienteering problem with time windows: an LP-based granular variable neighborhood search ⋮ Maximum weight relaxed cliques and Russian doll search revisited ⋮ Coloring the nodes of a directed graph ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ On risk-averse maximum weighted subgraph problems ⋮ An improved bit parallel exact maximum clique algorithm ⋮ A greedy algorithm to construct covering arrays using a graph representation ⋮ Reachability cuts for the vehicle routing problem with time windows ⋮ Combinatorial algorithms for the maximum \(k\)-plex problem ⋮ Risk transportation via a clique number problem formulation. ⋮ On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ Improvements to MCS algorithm for the maximum clique problem ⋮ The composition of semi-finished inventories at a solid board plant. ⋮ A simple simulated annealing algorithm for the maximum clique problem ⋮ Exploiting incomplete information to manage multiprocessor tasks with variable arrival rates ⋮ Exact algorithms for maximum clique: a computational study ⋮ A column generation and branch-and-cut algorithm for the channel assignment problem ⋮ A nearly optimal sensor placement algorithm for boundary coverage ⋮ Parallelization of a branch-and-bound algorithm for the maximum weight clique problem ⋮ Reduction of indefinite quadratic programs to bilinear programs ⋮ Decomposing clique search problems into smaller instances based on node and edge colorings ⋮ Detecting embedded Horn structure in propositional logic ⋮ PUSH: A generalized operator for the maximum vertex weight clique problem ⋮ Speeding up branch and bound algorithms for solving the maximum 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 ⋮ On the asymmetric representatives formulation for the vertex coloring problem ⋮ Variable neighborhood search for the maximum clique ⋮ A hybrid heuristic for the maximum clique problem ⋮ Clique-detection models in computational biochemistry and genomics ⋮ An exact bit-parallel algorithm for the maximum clique problem ⋮ A fast discovery algorithm for large common connected induced subgraphs ⋮ Optimal wafer cutting in shuttle layout problems ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems ⋮ Discrete Optimization with Decision Diagrams ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates ⋮ Greedy randomized adaptive search procedures ⋮ A branch-and-bound approach for maximum quasi-cliques

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Clique detection for nondirected graphs: Two new algorithms
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Finding a Maximum Clique in an Arbitrary Graph
• Determining the number of internal stability of a graph
• Finding a Maximum Independent Set
• On the complexity of approximating the independent set problem
• Algorithm 457: finding all cliques of an undirected graph
• On the theory of graphs

This page was built for publication: An exact algorithm for the maximum clique problem