A branch and bound algorithm for the maximum clique problem

DOI10.1007/BF01415983zbMath0701.90091OpenAlexW2009789570MaRDI QIDQ5899820

Luitpold Babel, Gottfried Tinhofer

Publication date: 1990

Published in: [https://portal.mardi4nfdi.de/entity/Q3031760 ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research] (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01415983

zbMATH Keywords

branch-and-bound algorithmcomputational resultsmaximum cliquecomplete subgraphbacktracking methods

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

An exact algorithm for the maximum stable set problem, Solving the maximum clique problem using a tabu search approach, A review on algorithms for maximum clique problems, On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem, An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network, Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, On the minimum number of logical clauses inferred from examples, Diversification strategies in tabu search algorithms for the maximum clique problem, Solving hard set covering problems, Variable neighborhood search for the maximum clique, Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering, An algorithm for finding a maximum clique in a graph, Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection, A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles, Enumerating all connected maximal common subgraphs in two graphs, Finding maximum cliques in arbitrary and in special graphs, A fast algorithm for the maximum weight clique problem, The maximum clique problem

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
• On maximal independent sets of vertices in claw-free graphs
• Clique detection for nondirected graphs: Two new algorithms
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Finding a Maximum Clique in an Arbitrary Graph
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Finding maximum cliques in circle graphs
• Determining the number of internal stability of a graph
• Algorithms on circular-arc graphs
• Vertex packings: Structural properties and algorithms
• Finding a Maximum Independent Set
• A node covering algorithm
• New methods to color the vertices of a graph
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithm 457: finding all cliques of an undirected graph