An improved bit parallel exact maximum clique algorithm

DOI10.1007/s11590-011-0431-yzbMath1268.90118MaRDI QIDQ1941191

Pablo San Segundo, Diego Rodriguez-Losada, Miguel Hernando, Fernando Matia

Publication date: 12 March 2013

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: http://oa.upm.es/11804/

zbMATH Keywords

graph; branch and bound; maximum clique; exact search

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

Related Items

A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs, An enhanced bitstring encoding for exact maximum clique search in sparse graphs, CliSAT: a new exact algorithm for hard maximum clique problems, Infra-chromatic bound for exact maximum clique search, A new exact maximum clique algorithm for large and massive sparse graphs, A parallel maximum clique algorithm for large and massive sparse graphs, Efficiently enumerating all maximal cliques with bit-parallelism, The maximum clique interdiction problem, Exact algorithms for maximum clique: a computational study, Multi-threading a state-of-the-art maximum clique algorithm, A new upper bound for the maximum weight clique problem, A new branch-and-bound algorithm for the maximum weighted clique problem, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, A branch-and-cut algorithm for the edge interdiction clique problem, A new branch-and-filter exact algorithm for binary constraint satisfaction problems, An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network, Relaxed approximate coloring in exact maximum clique search, A parallel branch and bound algorithm for the maximum labelled clique problem, Finding near-optimal independent sets at scale, A new branch-and-bound algorithm for the maximum edge-weighted clique problem, A review on algorithms for maximum clique problems, On the Power of Simple Reductions for the Maximum Independent Set Problem

Uses Software

• Chaff
• MaxCliqueDyn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact bit-parallel algorithm for the maximum clique problem
• An exact algorithm for the maximum clique problem
• An algorithm for finding a maximum clique in a graph
• A fast algorithm for the maximum clique problem
• Clique-detection models in computational biochemistry and genomics
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique