An exact algorithm for the maximum clique problem
From MaRDI portal
Publication:922964
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
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
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, On identifying dominant cliques., 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, An algorithm for finding a maximum clique in a graph, Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements, Distance-Based Clique Relaxations in Networks: s-Clique and s-Club, A clique search problem and its application to machine scheduling, A new table of permutation codes, Lower bound algorithms for multiprocessor task scheduling with ready times, A new branch-and-filter exact algorithm for binary constraint satisfaction problems, Construction of constant GC-content DNA codes via a variable neighbourhood search algorithm, Estimating clique size by coloring the nodes of auxiliary graphs, A maximum edge-weight clique extraction algorithm based on branch-and-bound, Algorithms for the generalized independent set problem based on a quadratic optimization approach, Improving heuristics for the frequency assignment problem, Novel approaches for analyzing biological networks, Test case generators and computational results for the maximum clique problem, Numerical experiments with LP formulations of the maximum clique problem, Generation of lower bounds for minimum span frequency assignment, A fast algorithm for the maximum weight clique problem, The maximum clique problem, Coloring the edges of a directed graph, Modelling competitive Hopfield networks for the maximum clique problem
Uses Software
Cites Work
- 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
- Unnamed Item
