Finding a Maximum Clique in an Arbitrary Graph

DOI10.1137/0215075zbMath0604.05024DBLPjournals/siamcomp/BalasY86OpenAlexW2043005464WikidataQ56210390 ScholiaQ56210390MaRDI QIDQ3741641

Chang-Sung Yu, Egon Balas

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215075

zbMATH Keywords

maximum cliqueimplicit enumerationvertex packingk-chromatic subgraphstriangulated subgraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (89)

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 ⋮ Solving the maximum clique problem using a tabu search approach ⋮ A generalization of chordal graphs and the maximum clique problem ⋮ Balanced independent and dominating sets on colored interval graphs ⋮ Vertex packing problem application to the design of electronic testing fixtures ⋮ Phased local search for the maximum clique problem ⋮ Chordal editing is fixed-parameter tractable ⋮ A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ An integer programming approach for solving the \(p\)-dispersion problem ⋮ Heuristics for the generalized median graph problem ⋮ An Efficient Approximation Algorithm for Finding a Maximum Clique Using Hopfield Network Learning ⋮ 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 ⋮ A graph-theoretic method for organizing overlapping clusters into trees, multiple trees, or extended trees ⋮ Maximal chordal subgraphs ⋮ 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 ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ Solving the anti-covering location problem using Lagrangian relaxation ⋮ A combinatorial column generation algorithm for the maximum stable set problem ⋮ A global optimization approach for solving the maximum clique problem ⋮ Ramsey theory and integrality gap for the independent set problem ⋮ Diversification strategies in tabu search algorithms for the maximum clique problem ⋮ An algorithm for finding a maximum weighted independent set in an arbitrary graph ⋮ Solving hard set covering problems ⋮ Branch-and-bound techniques for the maximum planar subgraph problem^∗ ⋮ Answering ``why empty? and ``why so many? queries in graph databases ⋮ A Max-SAT Inference-Based Pre-processing for Max-Clique ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ On risk-averse maximum weighted subgraph problems ⋮ Unnamed Item ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ On streaming algorithms for geometric independent set and clique ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ Distributed algorithms for maximum cliques ⋮ The discrete p-dispersion problem ⋮ Improvements to MCS algorithm for the maximum clique problem ⋮ An exact algorithm for the maximum clique problem ⋮ A simple simulated annealing algorithm for the maximum clique problem ⋮ The maximum clique interdiction problem ⋮ A branch and cut solver for the maximum stable set problem ⋮ Reduction of indefinite quadratic programs to bilinear programs ⋮ Fixed cardinality stable sets ⋮ Safe Lower Bounds for Graph Coloring ⋮ Decomposing clique search problems into smaller instances based on node and edge colorings ⋮ Genetic algorithmic approach to find the maximum weight independent set of a graph ⋮ Detecting embedded Horn structure in propositional logic ⋮ Speeding up branch and bound algorithms for solving the maximum clique problem ⋮ A parallel maximum clique algorithm for large and massive sparse graphs ⋮ A tutorial on branch and cut algorithms for the maximum stable set problem ⋮ A branch and bound algorithm for the maximum clique problem ⋮ A generalization of maximal independent sets ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ On the complexity of some subgraph problems ⋮ A branch and bound algorithm for the maximum clique problem ⋮ A set packing model for the ground holding problem in congested networks ⋮ Variable neighborhood search for the maximum clique ⋮ A branch-and-cut algorithm for the maximum cardinality stable set problem ⋮ Clique-detection models in computational biochemistry and genomics ⋮ Median graphs: A genetic approach based on new theoretical properties ⋮ An exact approach to the problem of extracting an embedded network matrix ⋮ A branch-and-price approach for the partition coloring problem ⋮ Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ Approximating the maximum vertex/edge weighted clique using local search ⋮ \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates ⋮ Counting clique trees and computing perfect elimination schemes in parallel ⋮ STABULUS: A technique for finding stable sets in large graphs with tabu search ⋮ Using Fifth Generation Tools for Solving the Clique Number Problem ⋮ TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph ⋮ An algorithm for finding a maximum clique in a graph ⋮ The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope ⋮ An analysis of parameter adaptation in reactive tabu search ⋮ Facets for node packing ⋮ On the lcm of the Differences of Eight Primes ⋮ Enumerating all connected maximal common subgraphs in two graphs ⋮ Test case generators and computational results for the maximum clique problem ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ A fast algorithm for the maximum weight clique problem ⋮ The maximum clique problem ⋮ An enhanced bitstring encoding for exact maximum clique search in sparse graphs ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches ⋮ Modelling competitive Hopfield networks for the maximum clique problem

This page was built for publication: Finding a Maximum Clique in an Arbitrary Graph