An algorithm for finding a maximum clique in a graph

DOI10.1016/S0167-6377(97)00054-0zbMath0908.90264OpenAlexW2002747011MaRDI QIDQ1267190

David R. Wood

Publication date: 6 October 1998

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(97)00054-0

zbMATH Keywords

branch-and-bound algorithmgraph algorithmvertex coloringmaximum clique problemfractional coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

A fast algorithm for the maximum clique problem, Reducing graph coloring to clique search, Towards objective measures of algorithm performance across instance space, A logical approach to efficient Max-SAT solving, Infra-chromatic bound for exact maximum clique search, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, Exploring the role of graph spectra in graph coloring algorithm performance, A Max-SAT Inference-Based Pre-processing for Max-Clique, An exact algorithm for the maximum probabilistic clique problem, An improved bit parallel exact maximum clique algorithm, Combinatorial algorithms for the maximum \(k\)-plex problem, Dispersion with connectivity in wireless mesh networks, Three approximation algorithms for solving the generalized segregated storage problem., A decomposition approach for commodity pickup and delivery with time-windows under uncertainty, Exact algorithms for maximum clique: a computational study, A nearly optimal sensor placement algorithm for boundary coverage, Co-2-plex vertex partitions, Finding quasi core with simulated stacked neural networks, An exact bit-parallel algorithm for the maximum clique problem, A constraint programming approach to extract the maximum number of non-overlapping test forms, Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound, Simple ingredients leading to very efficient heuristics for the maximum clique problem, ON PLANAR MEDIANOID COMPETITIVE LOCATION PROBLEMS WITH MANHATTAN DISTANCE, Estimating clique size by coloring the nodes of auxiliary graphs

Uses Software

• GAP
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding maximum cliques in arbitrary and in special graphs
• An exact algorithm for the maximum clique problem
• A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
• The maximum clique problem
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Finding a Maximum Clique in an Arbitrary Graph
• Finding a Maximum Independent Set
• New methods to color the vertices of a graph
• Algorithm 457: finding all cliques of an undirected graph
• A branch and bound algorithm for the maximum clique problem
• A branch and bound algorithm for the maximum clique problem