An improved bit parallel exact maximum clique algorithm

DOI10.1007/s11590-011-0431-yzbMath1268.90118OpenAlexW2008362324MaRDI 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

graphbranch and boundmaximum cliqueexact search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

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

Uses Software

• Chaff
• MaxCliqueDyn

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item